# Does an “efficient” random number generator exist?

Given some number $n$ and a seed number $s$<$n$, I want a random number generator (RNG) that will go through all integers `<$n$ before coming back to $s$. The resulting random number must be roughly uniformly distributed (which of course it will be if you go through the entire sequence, so I mean for any "large" subsequence) and roughly un-autocorrelated. Furthermore I want the RNG to be "efficient" in that it takes up little memory and little computation. Perhaps I can say that it is $O(1)$ w.r.t. $n$ in terms of memory and computation.

For instance, I can think of a RNG right now that will fulfill the former requirements, but not the latter: Create a list of all numbers $0$ through $n-1$. "Mark off" the seed number $s$. Then take a random number $r$ from a Mersenne Twister RNG, move $r$ numbers to the right and if that number hasn't been marked off report it back and then mark it off. Continue the process until you've marked off all numbers in the list. - This method will report back non-repeating, un-autocorrelated integers, but will be super memory and time intensive.

I imagine the ideal answer to be some sort of small equation to provide the next number in the sequence based upon this number (or perhaps the last few).

Can such a RNG be proven to exist? Are such specific RNGs know to exist? Can their existence be disproven?

Editorial note: If anyone reading has super edit power... please feel free to clean up my post to make me sound more mathy (I am but a lowly engineer). Retag me too please.

-
The question was discussed in mathoverflow.net/questions/29494 (see also mathoverflow.net/questions/26942). –  Wadim Zudilin Jul 21 '10 at 2:06
@Wadim: It's not the same question. He wants a RNG with one big orbit. –  Greg Kuperberg Jul 21 '10 at 3:06
Just in case anyone does not know about it, the standard place to look for discussion of random number generators is chapter 3, volume 2 of Knuth's book on the art of computer programming. (At least it used to be; I'm not sure how recently it has been updated.) –  Richard Borcherds Jul 21 '10 at 5:49
What you are looking for is not a PRNG but a random permutation ("shuffle") of the integers. This is actually covered in introductory algorithms classes - the usually solution is a LFSR, as mentioned by Yuval. You may also be interested to know that you solution is very close to the popular Knuth Shuffle (en.wikipedia.org/wiki/Knuth_shuffle) –  BlueRaja Jul 21 '10 at 6:36
@Greg - yep, that's right. –  John Berryman Jul 21 '10 at 11:25

Your requirements aren't rigorously stated, so it's hard to say what you can prove exists or doesn't exist. In the strictest sense, a pseudo-random number generator cannot possibly be "roughly uniformly distributed". Every PRNG is an expansion of entropy from its settings to the set of possible sequences, and it is easy to see for reasons similar to your comments about memory requirements that the set of possible sequences has vastly more entropy than the settings. What a PRNG really does is passes certain computationally feasible tests of randomness and not necessarily other tests.

There are conjectures in computer science that "one-way functions exist". Some of these conjecture would imply that there are PRNGs that look random for any polynomial-time test, and for some conjectures permutations that look random for any polynomial-time test. However, these conjectures are harder than the P vs NP problem, so no one is about to prove them. In any case, if you just want a PRNG for your own practical use, it's overkill to look for one that has been analyzed cryptographically.

It is known that modular exponentiation is a pretty good PRNG. If you want something that looks like a permutation, let $p$ be a prime number, and let $a$ be a carefully chosen residue mod $p$. (Carefully chosen means that $a$ should be a primitive residue far away from $0$.) Then the function $$f_a(k) = a^k \bmod p$$ is already statistically okay. This is a permutation of the numbers $1 \le k \le p-1$.

Now, the most common way to compute $f_a$ is to store $f_a(k)$ and then multiply by $a$ to get the next power. (As Richard Borcherds mentions, the iteration $x \mapsto ax+b \bmod n$ is a similar idea and a major standard, including in Knuth's book and in the Unix RNG "drand48".) However, these days that level of efficiency isn't so important, and it is interesting that you can compute $f_a$ directly by repeated squaring. So you can improve the strength of $f_a$ by making a composition such as $f_b(f_a(k)+c)$, where the addition is taken mod $p-1$. Or you could insert a more creative transformation. For instance, if $p$ is a Mersenne prime, then permuting the bits of $k$ is a simple transformation that can be inserted between applications of $f_a$.

If you want a permutation of some $n$ that is not of the form $p-1$, then you can find some prime $p > n$ that is not much larger and use the above same tricks. You can just skip values that are out of range.

Decades ago, I wanted a pseudo-random permutation for a scrambled screen fade in a computer game. I just used consecutive values of $f_a$ for some convenient modulus (which doesn't have to be prime; there are other variations) and it looked fine.

-
Very interesting. Do you have any references that I can look at for how/why this works? –  John Berryman Jul 21 '10 at 11:30
Why it gives you a permutation? The point is that $(\mathbb{Z}/p)^\times$ is a cyclic group. That's because $\mathbb{Z}/p$ is a field. The equation $x^k = a \mod p$ has at most $k$ roots for any $a$ and $k$, which forces a cyclic multiplicative structure. Why it has good randomness properties? Because decoding it is an example of "discrete logarithm". See en.wikipedia.org/wiki/Finite_field#Multiplicative_structure and en.wikipedia.org/wiki/Discrete_logarithm . –  Greg Kuperberg Jul 21 '10 at 14:08
You want to be careful about composing two good pseudorandom number generators as above: as Knuth points out in his book, this tends to give a terrible pseudorandom number generator with short periods. The point is that iterating a "randomly chosen" permutation is (paradoxically) a very poor pseudorandom number generator, as its cycle lengths will be on average rather short. –  Richard Borcherds Jul 21 '10 at 14:24
@borcherds: My suggestion is that the PRNG should store a counter rather than to compute an iteration. Composing iterations is a bad idea; composing one-use permutations is fine. –  Greg Kuperberg Jul 21 '10 at 14:29
@Greg Thank you! –  John Berryman Jul 21 '10 at 14:53

Knuth, the art of computer programming vol II theorem A section 3.2.1.2 gives conditions for a linear congruential sequence x -> ax+c mod m to cycle through all numbers mod m, which may be what you want as these are often reasonable pseudorandom number generators. The conditions are that c is coprime to m, and a-1 is a multiple of all divisors of m that are prime or 4.

-

I assume that n is a power of 2.

You can try an LFSR (check Wikipedia), but that will cycle (given the correct feedback) only over the non-zero integers in your range.

Another possibility is the map x += (x*x) | 5, where you can actually replace 5 with any number of the form 8n+5. I don't remember the reference for that.

-

If you need your random sequence unpredictable in a cryptographic sense, then take a look at the article How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle presented by Ben Morris, Phillip Rogaway and Till Stegers at the Crypto 2009 conference last year.

If you don't need cryptographic security, don't bother looking at the article, as other approaches will be much more efficient. By the way, given the cipher you get your random numbers by encrypting the sequence 0, 1, 2, 3, ... mod n and changing randomly the key whenever the current element of the sequence is 0 mod n.

-