A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),^{[1]} is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNGgenerated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.^{[2]}
PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms, which do not inherit the linearity of simpler PRNGs, are needed.
Good statistical properties are a central requirement for the output of a PRNG. In general, careful mathematical analysis is required to have any confidence that a PRNG generates numbers that are sufficiently close to random to suit the intended use. John von Neumann cautioned about the misinterpretation of a PRNG as a truly random generator, and joked that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."^{[3]}
YouTube Encyclopedic

1/5Views:102 680156 92723 8785408 230

✪ How to Generate Pseudorandom Numbers  Infinite Series

✪ Pseudorandom number generators  Computer Science  Khan Academy

✪ Coding Math: Episode 51  Pseudo Random Number Generators Part I

✪ Section 4.5 Pseudorandom Numbers

✪ Pseudo Random Number Generator  Applied Cryptography
Transcription
Contents
 1 Potential problems with deterministic generators
 2 Generators based on linear recurrences
 3 Cryptographically secure pseudorandom number generators
 4 BSI evaluation criteria
 5 Mathematical definition
 6 Early approaches
 7 Nonuniform generators
 8 See also
 9 References
 10 Bibliography
 11 External links
Potential problems with deterministic generators
In practice, the output from many common PRNGs exhibit artifacts that cause them to fail statistical patterndetection tests. These include:
 Shorter than expected periods for some seed states (such seed states may be called 'weak' in this context);
 Lack of uniformity of distribution for large quantities of generated numbers;
 Correlation of successive values;
 Poor dimensional distribution of the output sequence;
 The distances between where certain values occur are distributed differently from those in a random sequence distribution.
Defects exhibited by flawed PRNGs range from unnoticeable (and unknown) to very obvious. An example was the RANDU random number algorithm used for decades on mainframe computers. It was seriously flawed, but its inadequacy went undetected for a very long time.
In many fields, much research work prior to the 21st century that relied on random selection or on Monte Carlo simulations, or in other ways relied on PRNGs, is much less reliable than it might have been as a result of using poorquality PRNGs.^{[4]} Even today, caution is sometimes required, as illustrated by the following warning, which is given in the International Encyclopedia of Statistical Science (2010).^{[5]}
The list of widely used generators that should be discarded is [long] ... Check the default [PRNG] of your favorite software and be ready to replace it if needed. This last recommendation has been made over and over again over the past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago.
As an illustration, consider the widely used programming language Java. As of 2017^{[update]}, Java still relies on a linear congruential generator (LCG) for its PRNG;^{[6]}^{[7]} yet LCGs are of low quality—see further below.
The first PRNG to avoid major problems and still run fairly quickly was the Mersenne Twister (discussed below), which was published in 1998. Other highquality PRNGs have since been developed.
Generators based on linear recurrences
In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised linear congruential generators. The quality of LCGs was known to be inadequate, but better methods were unavailable. Press et al. (2007) described the result thus: "If all scientific papers whose results are in doubt because of [LCGs and related] were to disappear from library shelves, there would be a gap on each shelf about as big as your fist".^{[8]}
A major advance in the construction of pseudorandom generators was the introduction of techniques based on linear recurrences on the twoelement field; such generators are related to linear feedback shift registers.
The 1997 invention of the Mersenne Twister,^{[9]} in particular, avoided many of the problems with earlier generators. The Mersenne Twister has a period of 2^{19937}−1 iterations (≈4.3×10^{6001}), is proven to be equidistributed in (up to) 623 dimensions (for 32bit values), and at the time of its introduction was running faster than other statistically reasonable generators.
In 2003, George Marsaglia introduced the family of xorshift generators,^{[10]} again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests.^{[11]}^{[12]}^{[13]}
In 2006 the WELL family of generators was developed.^{[14]} The WELL generators in some ways improves on the quality of the Mersenne Twister—which has a toolarge state space and a very slow recovery from state spaces with a large number of zeros.
Cryptographically secure pseudorandom number generators
A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only negligible advantage in distinguishing the generator's output sequence from a random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to polynomial time in the size of the seed. Though a proof of this property is beyond the current state of the art of computational complexity theory, strong evidence may be provided by reducing the CSPRNG to a problem that is assumed to be hard, such as integer factorization.^{[15]} In general, years of review may be required before an algorithm can be certified as a CSPRNG.
Some classes of CSPRNGs include the following:
 stream ciphers
 block ciphers running in counter^{[16]} or output feedback mode
 PRNGs that have been designed specifically to be cryptographically secure, such as Microsoft's Cryptographic Application Programming Interface function CryptGenRandom, the Yarrow algorithm (incorporated in Mac OS X and FreeBSD), and Fortuna
 combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any detectable nonrandomness
 special designs based on mathematical hardness assumptions – Examples include the Micali–Schnorr generator,^{[17]} NaorReingold pseudorandom function and the Blum Blum Shub algorithm, which provide a strong security proof. Such algorithms are rather slow compared to traditional constructions, and impractical for many applications.
 generic PRNGs  It has been shown that a (cryptographically) secure PRNG can be constructed generically from any oneway function.^{[18]} However, this generic construction is extremely slow in practice, and is mainly of theoretical interest.
It has been shown to be likely that the NSA has inserted an asymmetric backdoor into the NIST certified pseudorandom number generator Dual_EC_DRBG.^{[19]}
Most PRNG algorithms produce sequences which are uniformly distributed by any of several tests. 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 highquality PRNG from a truly random sequence. In this setting, the distinguisher knows that either the known PRNG algorithm was used (but not the state with which it was initialized) or a truly random algorithm was used, and has to distinguish between the two.^{[20]} 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 use of a truly random sequence. The simplest examples of this dependency are stream ciphers, which (most often) work by exclusive oring the plaintext of a message with the output of a PRNG, producing ciphertext. The design of cryptographically adequate PRNGs is extremely difficult, because they must meet additional criteria. The size of its period is an important factor in the cryptographic suitability of a PRNG, but not the only one.
BSI evaluation criteria
The German Federal Office for Information Security (Bundesamt für Sicherheit in der Informationstechnik, BSI) has established four criteria for quality of deterministic random number generators.^{[21]} They are summarized here:
 K1 – There should be a high probability that generated sequences of random numbers are different from each other.
 K2 – A sequence of numbers which is indistinguishable from 'true random' numbers according to specified statistical tests. The tests are the monobit test (equal numbers of ones and zeros in the sequence), poker test (a special instance of the chisquared test), runs test (counts the frequency of runs of various lengths), longruns test (checks whether there exists any run of length 34 or greater in 20 000 bits of the sequence)—both from BSI^{[21]} and NIST,^{[22]} and the autocorrelation test. In essence, these requirements are a test of how well a bit sequence: has zeros and ones equally often; after a sequence of n zeros (or ones), the next bit a one (or zero) with probability onehalf; and any selected subsequence contains no information about the next element(s) in the sequence.
 K3 – It should be impossible for any attacker (for all practical purposes) to calculate, or otherwise guess, from any given subsequence, any previous or future values in the sequence, nor any inner state of the generator.
 K4 – It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.
For cryptographic applications, only generators meeting the K3 or K4 standard are acceptable.
Mathematical definition
Given
 – a probability distribution on (where is the standard Borel set on the real line)
 – a nonempty collection of Borel sets , e.g. . If is not specified, it may be either or , depending on context.
 – a nonempty set (not necessarily a Borel set). Often is a set between 's support and its interior; for instance, if is the uniform distribution on the interval , might be . If is not specified, it is assumed to be some set contained in the support of and containing its interior, depending on context.
We call a function (where is the set of positive integers) a pseudorandom number generator for given taking values in iff
( denotes the number of elements in the finite set .)
It can be shown that if is a pseudorandom number generator for the uniform distribution on and if is the CDF of some given probability distribution , then is a pseudorandom number generator for , where is the percentile of , i.e. . Intuitively, an arbitrary distribution can be simulated from a simulation of the standard uniform distribution.
Early approaches
An early computerbased PRNG, suggested by John von Neumann in 1946, is known as the middlesquare method. The algorithm is as follows: take any number, square it, remove the middle digits of the resulting number as the "random number", then use that number as the seed for the next iteration. For example, squaring the number "1111" yields "1234321", which can be written as "01234321", an 8digit number being the square of a 4digit 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.
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 then available, 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 hundred times faster than reading numbers in from punched cards.
The middlesquare method has since been supplanted by more elaborate generators.
A recent innovation is to combine the middle square with a Weyl sequence. This method produces high quality output through a long period. See Middle Square Weyl Sequence PRNG.
Nonuniform generators
Numbers selected from a nonuniform probability distribution can be generated using a uniform distribution PRNG and a function that relates the two distributions.
First, one needs the cumulative distribution function of the target distribution :
Note that . Using a random number c from a uniform distribution as the probability density to "pass by", we get
so that
is a number randomly selected from distribution .
For example, the inverse of cumulative Gaussian distribution with an ideal uniform PRNG with range (0, 1) as input would produce a sequence of (positive only) values with a Gaussian distribution; however
 When using practical number representations, the infinite "tails" of the distribution have to be truncated to finite values.
 Repetitive recalculation of should be reduced by means such as ziggurat algorithm for faster generation.
Similar considerations apply to generating other nonuniform distributions such as Rayleigh and Poisson.
See also
 List of pseudorandom number generators
 Applications of randomness
 Lowdiscrepancy sequence
 Pseudorandom binary sequence
 Pseudorandom noise
 Random number generation
 Random number generator attack
 Randomness
 Statistical randomness
References
 ^ Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 80057. NIST. Retrieved 19 August 2013.
 ^ "Pseudorandom number generators". Khan Academy. Retrieved 20160111.
 ^ Von Neumann, John (1951). "Various techniques used in connection with random digits" (PDF). National Bureau of Standards Applied Mathematics Series. 12: 36–38.
 ^ Press et al. (2007), chap.7
 ^ L'Ecuyer P. (2010), "Uniform random number generators", International Encyclopedia of Statistical Science (editor—Lovric M.) Springer.
 ^ Random (Java Platform SE 8), Java Platform Standard Edition 8 Documentation.
 ^ Random.java at OpenJDK.
 ^ Press et al. (2007) §7.1
 ^ Matsumoto, Makoto; Nishimura, Takuji (1998). "Mersenne twister: a 623dimensionally equidistributed uniform pseudorandom number generator" (PDF). ACM Transactions on Modeling and Computer Simulation. ACM. 8 (1): 3–30. doi:10.1145/272991.272995.
 ^ Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software. 8 (14).
 ^ S.Vigna. "xorshift*/xorshift+ generators and the PRNG shootout".
 ^ Vigna S. (2016), "An experimental exploration of Marsaglia’s xorshift generators", ACM Transactions on Mathematical Software, 42; doi:10.1145/2845077.
 ^ Vigna S. (2017), "Further scramblings of Marsaglia’s xorshift generators", Journal of Computational and Applied Mathematics, 315; doi:10.1016/j.cam.2016.11.006.
 ^ Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (2006). "Improved longperiod generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. doi:10.1145/1132973.1132974.
 ^ Song Y. Yan. Cryptanalytic Attacks on RSA. Springer, 2007. p. 73. ISBN 9780387487410.
 ^ Niels Ferguson, Bruce Schneier, Tadayoshi Kohno (2010). "Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator" (PDF).CS1 maint: Multiple names: authors list (link)
 ^ Klaus Pommerening (2016). "IV.4 Perfect Random Generators". Cryptology. unimainz.de. Retrieved 20171112.
The MICALISCHNORR generator
 ^ Pass, Rafael. "Lecture 11: The GoldreichLevin Theorem" (PDF). COM S 687 Introduction to Cryptography. Retrieved 20 July 2016.
 ^ Matthew Green. "The Many Flaws of Dual_EC_DRBG".
 ^ Katz, Jonathan; Yehuda, Lindell (2014). Introduction to modern cryptography. CRC press. p. 70.
 ^ ^{a} ^{b} Schindler, Werner (2 December 1999). "Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators" (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. pp. 5–11. Retrieved 19 August 2013.
 ^ "Security requirements for cryptographic modules". FIPS. NIST. 19940111. p. 4.11.1 Power–Up Tests. Archived from the original on May 27, 2013. Retrieved 19 August 2013.
Bibliography
 Barker E., Kelsey J., Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST SP80090A, January 2012
 Brent R.P., "Some longperiod random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
 Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
 Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, SpringerVerlag.
 Knuth D.E.. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. AddisonWesley, 1997. ISBN 0201896842. Chapter 3. [Extensive coverage of statistical tests for nonrandomness.]
 Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. ISBN 9780691025469
 von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 3638.
 Peterson, Ivars (1997). The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. ISBN 0471164496.
 Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
 Viega J., "Practical Random Number Generation in Software", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
External links
 TestU01: A free, stateoftheart (GPL) C++ Random Number Test Suite.
 DieHarder: A free (GPL) C Random Number Test Suite.
 "Generating random numbers" (in embedded systems) by Eric Uner (2004)
 "Analysis of the Linux Random Number Generator" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006)
 "Better pseudorandom generators" by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan (Microsoft Research, 2012)
 rand() Considered Harmful on YouTube by Stephan Lavavej (Microsoft, 2013)