# Could PRNGs make use of more internal state?

In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing):

Pseudo-random number generators (PRNGs) must have a period since they only have finitely many internal states.

At least for the PRNGs we see in the class, this is certainly a valid argument (assuming a finite target interval). But it begs the question: why do they not use more memory resp. internal state?

Going through this list, it seems to be the case that all PRNGs do indeed use only a few numbers from the target interval (plus some magic constants).

• Most use one to $\approx$ 5 of the most recently generated numbers.
• Some have parameter that controls how many values to store ("$r$-lag").
• A few use rather many numbers (but still constantly many).

The one I can't quite place is Naor-Reingold; I can't tell how it would be used to generate an actual sequence of pseudo-random numbers.

So while the memory usage (i.e. internal state size) of known/used PRNGs depends on the target interval and internal constants, it does not on the amount of (already) generated numbers.

Have there been any attempts to use more memory in order to obtain better generators? If so, why does it not help or not work at all?

• Naor-Rheingold appears to be fairly straightforward. See the example on the wikipedia page: f(5) = 4 and you can trivially calculate f(6), but you can't calculate f_inv(4) = 5 other than brute-forcing it. Thus, you can't predict what follows 4. Jan 13 '16 at 12:24

Because, for any practical purpose, a PRNG with sufficiently, but finitely many states is indistinguishable from one with infinitely many. Mersenne Twister has a period of $2^{19937} - 1$, [insert your favorite argument about why $2^{19937}$ is a somewhat large number here].