show/hide this revision's text 2 added 257 characters in body

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 \pmod 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.
show/hide this revision's text 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 carefully chosen residue mod $p$. Then the function $$f_a(k) = a^k \pmod 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. 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.