| Pseudo-random Number Generator |
Website Links For Pseudorandom |
Information AboutPseudo-random Number Generator |
| CATEGORIES ABOUT PSEUDORANDOM NUMBER GENERATOR | |
| pseudorandom number generators | |
|
John Von Neumann put essentially the same idea in a slightly different way, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." 2 Most pseudo-random algorithms produce sequences which are Uniformly Distributed by any of several tests. Common classes of these algorithms are Linear Congruential Generator s, Lagged Fibonacci Generator s, Linear Feedback Shift Register s and generalised feedback shift registers. Recent instances of pseudo-random algorithms include Blum Blum Shub , Fortuna , and the Mersenne Twister . INHERENT NONRANDOMNESS Because any PRNG run on a . It is certain that if such a generator uses only a fixed amount of memory that, given a sufficient number of iterations, the generator will revisit a previous internal state, after which it will repeat forever. A generator that isn't periodic can be designed, but its memory requirements would grow without limit 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. The unacceptable significance of this periodicity can sometimes be avoided in practice. The length of the maximum period doubles with each bit of added memory, and it is thus easy to build PRNGs with periods so long that no computer could complete a single cycle in the expected lifetime of the universe. 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 well-designed PRNG from a truly random sequence (ie, White Noise ) without knowing, for instance, the algorithm and the seed with which it was initialized. Most cryptography relies on the assumption that it is infeasible to distinguish a suitable PRNG from a random sequence; the simplest example of this dependency is a Stream Cipher , which (most often) works by taking the Exclusive Or of the secret message with the output of a PRNG. The design of such PRNGs is extremely difficult, and most programs use much simpler PRNGs, even some cryptographic systems which should certainly not. The algorithm of R P Brent can be used to determine the period length of determinstic generator algorithms; the result may surprise, but can be used to assist in evaluating the acceptability of a generator algorithm to a particular use. PROBLEMS WITH DETERMINISTIC GENERATORS In practice, many common PRNGs exhibit Artifact s which cause them to fail statistically significant tests. These include, but are certainly not limited to:
Defects exhibited by a flawed PRNG may range from unnoticeable to completely absurd. The RANDU random number algorithm used for decades on Mainframe Computer s 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 traced to inadequate generators, which in turn sometimes leads to improvements in PRNGs. EARLY APPROACHES An early computer-based PRNG was suggested by used numbers of 10 digits in length, but the process was the same. The problem with the "middle square" method is that even the best sequences must eventually repeat themselves, some doing so very quickly. Some sequences, such as "0000", will repeat quite promptly. Von Neumann was aware of such things, but for his purposes he found the approach sufficient, and its errors easy to detect (he was worried that mathematical "fixes" would simply hide the errors rather than get rid of them). On the ENIAC computer which he was using, the "middle square" method generated numbers at a rate some two hundred times more quickly than reading numbers from Punch Card s. In Von Neumann's view, hardware random number generators were questionable, because if they did not record the numbers generated, they could not later be tested for errors. If they did record their numbers, they would exhaust computer memories of the time, and the computer's ability to read and write numbers. If the numbers were written to cards, they would take much longer to write and read. The middle-square method has been supplanted for most purposes by more elaborate generators. MERSENNE TWISTER The 1997 recent invention of the Mersenne Twister algorithm, by Makoto Matsumoto and Takuji Nishimura, avoids most of the problems with earlier generators. It has the colossal period of 219937-1 iterations (probably more than the number of computations which can be performed for 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 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 algorithm and to recognize the numbers as being non-random (as with the Berlekamp-Massey Algorithm or an extension from it, such as the Reed-Sloane Algorithm ). At this time this has had no known negative operational effects save making the Mersenne Twister unusable as a cryptographically secure PRNG. A PEN-AND-PAPER METHOD The decimal expansion of reciprocal of the form 1/q, for "suitable" values of q provides an easily-implemented source of (pseudo-)random numbers {Link without Title} . Matthews showed that a sufficient condition for the method to produce a stream of 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 can be summed up simply: a CSPRNG should appear indistinguishable from random on ''any'' examination, whereas normally a PRNG is only required to appear random to standard statistical tests. However, there are generator designs which meet this criterion, but which are 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
|
|
|