Does an "efficient" random number generator exist?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

I think the word "efficient" in random generators meant that your generators should have some properties like :

• Pass empirical statistical tests
• Mathematical basis
• Reproducibility
• easy to use in parallel computation

you can check SFMT (twice faster than Mersenne Twister) ,it is one of the best. you can check SFMT here