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.



Does an "efficient" random number generator exist?
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.


