About Opentopia
Opentopia Directory Encyclopedia Tools

Pseudorandom number generator

Encyclopedia : P : PS : PSE : Pseudorandom number generator

A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers which are not truly random. The outputs of pseudorandom number generators only approximate some of the properties of random numbers. Although truly random numbers are believed to be generatable using hardware random number generators, pseudo-random numbers are important in practice for simulations (eg, of physical systems with the Monte Carlo method), and are central in the practice and so in the theory of cryptography. Careful mathematical analysis is required to have any confidence a PRNG generates numbers that are sufficiently "random" to suit the intended use. Robert R. Coveyou of Oak Ridge National Laboratory once titled an article, "The generation of random numbers is too important to be left to chance."1 and John von Neumann put essentially the same idea in a slightly more colorful way, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."2

Most pseudo-random generator algorithms produce sequences which are uniformly distributed by any of several tests. Common classes of these algorithms are linear congruential generators, lagged Fibonacci generators, linear feedback shift registers and generalised feedback shift registers. Recent instances of pseudo-random algorithms include Blum Blum Shub, Fortuna, and the Mersenne twister.

Contents

Inherent nonrandomness

Because any PRNG run on a deterministic computer (contrast quantum computer) is necessarily a deterministic algorithm, its output will inevitably have one property that a true random sequence can never have: periodicity. It is certain that, if such a generator has only a finite memory, it will, given sufficient time, revisit a previous internal state, after which it will repeat the prior sequence forever. Non-periodic generators for deterministic computers can be designed, but memory requirements would grow without limit during runs; this is not, of course, possible in real equipment. A PRNG can be started from an arbitrary starting point, using a 'random' seed state; it will always produce the same sequence thereafter when initialized with that state.

The undesirable consequences of this periodicity can sometimes be avoided in practice. The length of the maximum period typically doubles with each bit of 'state' added, and it is thus relatively easy to build PRNGs with periods so long no computer could complete a single period in the expected lifetime of the universe, and this is sufficient in some applications. It is an open question, and one central to the theory and practice of cryptography, whether there is any way to distinguish the output of a high-quality PRNG from a truly random sequence (ie, white noise or its equivalent) without knowing, for instance, the algorithm(s) used and the state with which it was initialized. The security of most cryptographic algorithms and protocols using PRNGs is based on the assumption that it is infeasible to distinguish use of a suitable PRNG from a random sequence. The simplest examples of this dependency are stream ciphers, which (most often) works by exclusive oring the plaintext of a message with the output of a PRNG, producing ciphertext. The design of adequate PRNGs is extremely difficult, and most programs use simpler PRNGs, even some cryptosystems which should certainly not do so.

R P Brent's algorithm can be used to determine the period length of deterministic PRNGs; the result may be surprising, but they can be used to assist in evaluating the acceptability of a PRNG algorithm to a particular use.

Problems with deterministic generators

In practice, the output from many common PRNGs exhibit artifacts which cause them to fail statistical pattern detection tests. These include, but are certainly not limited to 
Defects exhibited by flawed PRNGs range from unnoticeable to absurdly obvious. The RANDU random number algorithm used for decades on mainframe computers was seriously flawed, and much research work of that period is less reliable than it might have been, and should have been, as a result. Sometimes, but not always, problems with models are noticed and traced to inadequate generators, which in turn sometimes leads to improvements in PRNGs. This is certainly not as often noticed as it should be, and so it is better to use good PRNGs from the beginning.

Early approaches

An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method. It is very simple: take any number, square it, remove the middle digits of the resulting number as your "random number", then use that number as the seed for the next iteration. For example, squaring the number "1111" yields "1234321", which might can be written as "01234321", an 8-digit number being the square of a 4-digit number. This gives "2343" as the "random" number. Repeating this procedure gives "4896" as the next result, and so on. Von Neumann used 10 digit numbers, but the process was the same.

A problem with the "middle square" method is that all sequences eventually repeat themselves, some very quickly, such as "0000". Von Neumann was aware of this, but he found the approach sufficient for his purposes, and was worried that mathematical "fixes" would simply hide errors rather than remove them. The middle square method's errors are easy to detect.

Von Neumann judged hardware random number generators unsuitable, for, if they did not record the output generated, they could not later be tested for errors. If they did record their output, they would exhaust the limited computer memories available then, and so the computer's ability to read and write numbers. If the numbers were written to cards, they would take very much longer to write and read. On the ENIAC computer he was using, the "middle square" method generated numbers at a rate some two hundred times faster than reading numbers in from punch cards.

The middle-square method has been supplanted for most purposes by more elaborate generators.

Mersenne twister

The 1997 invention of the Mersenne twister algorithm, by Makoto Matsumoto and Takuji Nishimura, avoids many of the problems with earlier generators. It has the colossal period of 219937-1 iterations (likely more than the number of computations which could be performed within the entire future existence of the universe), is proven to be equidistributed in (up to) 623 dimensions (for 32-bit values), and runs faster than all but the least statistically reasonable 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 algorithm and to detect that it is non-random (as with the Berlekamp-Massey algorithm or an extension of it, such as the Reed-Sloane algorithm). Till 2006, this has had no known negative operational effects for most purposes, save making the Mersenne Twister unusable as a cryptographically secure PRNG.

A pen-and-paper method

The decimal expansion of a reciprocal of the form 1/q, for "suitable" values of q, provides an easily-implemented source of (pseudo-)random numbers [link]. Matthews showed that a sufficient condition for the method to produce a stream of high quality random numbers of length q - 1 is that q = 2S + 1 where S is a Sophie Germain prime, such that both S and 2S + 1 are prime, with S being of the form 3, 9 or 11 mod 20. Thus “suitable” prime numbers q are 7, 23, 47, 59, 167, 179, etc (corresponding to S = 3, 11, 23, 29, 83, 89, etc.). The result is a stream of length q - 1 digits (including leading zeros). So, for example, using q = 23 generates the random digits 0,4,3,4,7,8,2,6.....3,9,1,3.

Cryptographically secure pseudorandom number generators

Main article: Cryptographically secure pseudo-random number generator
A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). The chief difference between a PRNG and a CSPRNG is simple: a CSPRNG should appear indistinguishable from random on any examination, whereas a PRNG is normally only required to appear to be random to standard statistical tests. However, there are generator designs which meet this criterion, but which are nevertheless not cryptographically strong.

Some classes of CSPRNGs include the following:

Evaluation criteria example

The German Institute for Security in Information Technology has established a four part criteria for quality of deterministic random number generators. They are summarized here:

For cryptographic applications, only generators meeting the K4 standard are really acceptable.

See also

Notes

1 Peterson. Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6

2 "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951).

References

External links

 

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles
0123456789
ABCDEFGHIJ
KLMNOPQRST
UVWXYZ?

E-mail this article to:

Personal Message: