# Questions tagged [pseudo-random-generators]

Questions about algorithms that deterministically generate sequences of numbers that have stochastic properties of random sequences.

93 questions
Filter by
Sorted by
Tagged with
38 views

### Predicting the next number output by a random number generator

Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence? For example, ...
125 views

### Why is the period of Mersenne Twister prng $2^{19937}-1$ and not $2^{19968}$?

For the Mersenne Twister prng, wikipedia, I feel the period exponent should be the size of the MT array, $32\cdot 624 = 19968$. How come the exponent is 19937 instead?
66 views

### How Fibonacci LFSR work

What is "Fibonacci" about the Fibonacci LFSR? If I read right, Fibonacci LFSR means that it depends on its two last states, but from the example in Wikipedia it doesn't look like two states are taken ...
35 views

### Kolmogorov randomness for Pseudo random number generator

I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable. So would appreciate ...
41 views

### Concatenated pseudorandom generators

I have two pseudorandom generators $G_1$ and $G_2$ from $k$ bit to $2k$ bit. I have another PRG $G_3$ from $k$ to $2k$ bits. Now I buildup a new function from $k$ to $4k$ as follows: Let $x$ be $k$ ...
37 views

### Pseudo random generator that is non injective

I was reading answer to https://crypto.stackexchange.com/questions/24941/prove-there-is-prg-that-is-not-necessarily-one-to-one Here assuming existence of G: from n bit to l(n) bits non injective G' ...
713 views

### Introductory Book on Pseudo-Random Number Generation

I'm a rank amateur in the area of pseudo-random number generation. I've recently found out that certain generators are better than others (e.g. mt19337 vs rand in C++) and learned what modulo bias is. ...
2k views

### Simulating a probability of 1 of 2^N with less than N random bits

Say I need to simulate the following discrete distribution: $$P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if k = 1} \\ 1 - \frac{1}{2^N}, & \text{if k = 0} \end{cases}$$ The most ...
34 views

### How good (or bad) is my makeshift PRNG?

Say I have designed a makeshift PRNG for my personal amusement, now I would like to see how good it is. How do I benchmark its "randomness"? Ideally, I want to know a statistics test, such that if I ...
53 views

### Can the pseudo-random-sequence generator be described as a finite state automaton?

I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot ...
26 views

### arithmetic coding for generating random number with desired distribution

Hi i want to convert random number with uniform distribution to desired distribution using arithmetic coding. It has been done in the following research paper called arithmetic distribution coding ...
28 views

### What is a minimal, pseudo-random hash function?

I want to generate pseudo-random hashes of inputs in a way that is optimally time and space efficient. I'm not at all concerned about security. The output should be evenly distributed and appear ...
320 views

### Are there pseudorandom number generators (PRNG) with no finite period?

The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period? For this question it is not ...
54 views

### PRNG for a gaussian distribution?

I need suggestions for algorithm for Pseudo random number generators that will produce a near gaussian distribution (bell curve) for automatically generating test data. I know that PRNG produce ...
46 views

### Why do many developers continue to rely on pseudo-random number generators?

Although hardware based “true” random number generators are available, software-based pseudo-random number generators still remain the predominant method for generating random numbers in use today. ...
32 views

### Is it possible to build a secure PRG from two functions one of them being a PRG?

Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG. Being $\alpha$ a constant, is it possible ...
47 views

### A question about the definition of PRFs

Let $\mathcal{F} = \{ f_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$. We define a family of ...
195 views

### How to determine seed collision probability in a PRNG?

I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds ...
64 views

### What is known about the equidistribution properties of Philox pseudo random number generator?

I want to evaluate the usefulness of Philox pseudo random number generator for drawing multidimensional random vectors. What is known about the equidistribution properties of Philox? I read the ...
18 views

### Pseudo-random regex-searchable function

Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties: $f$ is efficiently ...
1k views

### Given a random number generator rand5() generate gen7()

Given a pseudo random number generator rand5() that generates a random integer in the set [0,1,2,3,4], how would someone use this to generate a function rand7() that outputs [0,1,2,3,4,5,6] with equal ...
50 views

### Generate numeric or string ID for a sequence of elements

How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter. Example: [41,1001,32] should generate the ...
55 views

### Why does the distribution of pseudorandom numbers change when operating like this?

We were introduced to the standard C rand() function, and how to use it. At some point during the class we were asked how to roll a die. The simple answer was to ...
246 views

### Perfect random number generation using normal numbers

This paper describes a computable normal number. One property of normal numbers is that, written in binary, the $i^{th}$ bit is equally likely to be 0 or 1 (in the sense that as $n$ gets large, the ...
53 views

### Can pseudo random number generator generate all possible sequences?

Suppose I have a random number generator G that takes in a seed s from the set of integers. Suppose we have a sequence of numbers Q where |Q| = k. Does there exist a seed s such that G(s) produces the ...
27 views

### Pseudo-number generation compared to Blum-Micali

A few years ago I made a pseudo-random number generator to use in a monte carlo simulation for a lecture in my University. My instructor ask me why I did that generator instead of using C equivalent ...
58 views

82 views

### Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness?

I'm looking for a small function from integers to integers - in a language that only has floats - that can act as a visual RNG. Normally I would use a function such as the one described here: ...
19 views

### Generating symmetric keys

Let's assume that we have to generate huge number of 256-bit symmetric keys. How to do it and how to be sure that it is safe. Perhaps it requires a strong mathematical backend. Don't hesitate to ...
473 views

### What does it mean for a random number generator's sequence to be only 1-dimensionally equidistributed?

Whilst reading up on Xorshift I came across the following (emphases added): The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2^128 − 1 and passes BigCrush: ...
562 views

### Non repeating pseudo random number generator for a dynamic range

Algorithms like Knuth's algorithm or this one, works for a range that is known in advance(like shuffling numbers 1 to 11), in this case the range will never change. You'll always get a random no. ...
57 views

### What is the period of N xored identical random number generators, with differing seeds?

This question is a kinda spin off from Why do we not combine random number generators? If for example we had N identical type random number generators, with N different seeds, what would the period ...
30 views

### Generation of 11 bit random number

I need camera to sign one random line(there are something like 2000 lines) from the frame each second. At the beginning I have some 64 bits seed with high entropy from physical RNG and a secure ...
62 views

### Fitting a feedback loop to data points

If you want to fit a polynomial to a set of data points, there are many options available including least squares fitting, gradient descent, and lagrange interpolation. However, thinking in more ...
150 views

### Existence of suitable pseudo-random number generators to derandomize BPP to P

I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...
59 views

4k views

### Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...