Pseudorandom number generator

Helping orphans the way you would do it

A pseudorandom number generator (PRNG) is an algorithm which generates a sequence of numbers, the elements of which are approximately independent of each other.

The outputs of pseudorandom number generators are not truly random—they only approximate some of the properties of random numbers. John von Neumann emphasized this with the remark "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin". While there have been attempts to generate "truly random" numbers, using hardware random number generators, pseudorandom numbers are a critical part of modern computing, from cryptography to the Monte Carlo method for simulating physical systems. Careful mathematical analysis is required to ensure that the generated numbers are sufficiently "random;" as Robert R. Coveyou of Oak Ridge National Laboratory once remarked, "The generation of random numbers is too important to be left to chance."

Most such algorithms attempt to produce samples that are uniformly distributed. Common classes of algorithms are linear congruential generators, lagged Fibonacci generators, linear feedback shift registers and generalised feedback shift registers. Recent instances of algorithms include Blum Blum Shub, Fortuna, and the Mersenne Twister.

Table of contents

1 Inherent nonrandomness
2 Mersenne Twister
3 Cryptographically secure pseudorandom number generators
4 See also
5 References

Inherent nonrandomness

Because any PRNG run on a deterministic computer (contrast quantum computer) is a deterministic algorithm, its output will inevitably have certain properties that a true random sequence would not exhibit. One of these is guaranteed periodicity—it is certain that if the generator uses only a fixed amount of memory then, given a sufficient number of iterations, the generator will revisit the same internal state twice, after which it will repeat forever. A generator that isn't periodic can be designed, but its memory requirements would grow as it ran. In addition, a PRNG can be started from an arbitrary starting point, or seed state, and will always produce an identical sequence from that point on.

In practice, many PRNGs exhibit artifactss which can cause them to fail statistically significant tests. These include, but are certainly not limited to:

Shorter than expected periods for some seed states (not full period)
Poor dimensional distribution
Successive values are not independent
Some bits may be 'more random' than others
Lack of uniformity

Defects exhibited by a flawed PRNG may range from unnoticeable to ridiculous. The RANDU random number algorithm used for decades on mainframe computers was flawed, and much research work of that time is less reliable than it should have been as a result. Sometimes, but not always, modeling problems are noticed and lead to improvements in PRNGs.

Mersenne Twister

The recent invention of the Mersenne Twister algorithm, by Makoto Matsumoto and Takuji Nishimura in 1997, avoids most of these problems. It has a colossal period of 2¹⁹⁹³⁷-1 iterations, is proven to be equidistributed in 623 dimensions (for 32-bit values), and runs faster than all but the least statistically desirable generators. It is now increasingly becoming the "random number generator of choice" for statistical simulations and generative modeling.

However, it is possible to efficiently analyze the output of the Mersenne Twister and recognize the numbers as being non-random (as with the Berlekamp-Massey algorithm or an extension from it, such as the Reed-Sloane algorithm).

Cryptographically secure pseudorandom number generators

Main article: Cryptographically secure pseudo-random number generator

A PRNGs that is suitable for cryptographic applications is called a cryptographically secure PRNGs (CSPRNGs). They should not only evade statistical analysis but satisfy some cryptographic requirements.

Some classes of CSPRNGs include the following:

Stream ciphers, including block ciphers running in CTR mode.
Special designs with (some) security proof. For example Blum Blum Shub has a strong security proofs, though it is slow.
Finally, there are PRNGs that have been designed specifically to be cryptographically secure. One example is ISAAC. Which is fast and whose security recommendations features, among others, a very large expected cycle time.

References

Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition (Addison-Wesley, Boston, 1998).
The GNU Scientific Library, http://www.gnu.org/software/gsl/. A free (GPL) (C library that includes a number of PRNG algorithms.