A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),^{[1]} is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state, which includes a truly random seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom numbers are important in practice for their speed in number generation and their reproducibility, and they are thus central in applications such as simulations (e.g., of physical systems with the Monte Carlo method), in cryptography, and in procedural generation. Good statistical properties are a central requirement for the output of a PRNG, and common classes of suitable algorithms include linear congruential generators, lagged Fibonacci generators, and linear feedback shift registers. Cryptographic applications require the output to also be unpredictable, and more elaborate designs, which do not inherit the linearity of simpler solutions, are needed. More recent instances of PRNGs with strong randomness guarantees are based on computational hardness assumptions, and include the Blum Blum Shub, Fortuna, and Mersenne Twister algorithms.
In general, careful mathematical analysis is required to have any confidence that a PRNG generates numbers that are sufficiently "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."^{[2]} 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."^{[3]}
Mathematical definition
Given
 $P$  a probability distribution on $\backslash left(\backslash mathbb\{R\},\backslash mathfrak\{B\}\backslash right)$ (where $\backslash mathfrak\{B\}$ is the standard Borel field on the real line)
 $\backslash mathfrak\{F\}$  a nonempty collection of Borel sets $\backslash mathfrak\{F\}\backslash subseteq\backslash mathfrak\{B\}$, e.g. $\backslash mathfrak\{F\}=\backslash left\backslash \{\backslash left(\backslash infty,t\backslash right]:\; t\backslash in\backslash mathbb\{R\}\backslash right\backslash \}$. If $\backslash mathfrak\{F\}$ is not specified, it may be either $\backslash mathfrak\{B\}$ or $\backslash left\backslash \{\backslash left(\backslash infty,t\backslash right]:\; t\backslash in\backslash mathbb\{R\}\backslash right\backslash \}$, depending on context.
 $A\backslash subseteq\backslash mathbb\{R\}$  a nonempty set (not necessarily a Borel set). Often $A$ is a set between $P$'s support and its interior, for instance, if $P$ is the uniform distribution on the interval $\backslash left(0,1\backslash right]$, $A$ might be $\backslash left(0,1\backslash right]$. If $A$ is not specified, it is assumed to be some set contained in the support of $P$ and containing its interior, depending on context.
we call a function $f:\backslash mathbb\{N\}\_1\backslash rightarrow\backslash mathbb\{R\}$ (where $\backslash mathbb\{N\}\_1=\backslash left\backslash \{1,2,3,\backslash dots\backslash right\backslash \}$ is the set of positive integers) a pseudorandom number generator for $P$ given $\backslash mathfrak\{F\}$ taking values in $A$ iff
 $f\backslash left(\backslash mathbb\{N\}\_1\backslash right)\backslash subseteq\; A$
 $\backslash forall\; E\backslash in\backslash mathfrak\{F\}\backslash forall\; 0<\backslash varepsilon\backslash in\backslash mathbb\{R\}\backslash exists\; N\backslash in\backslash mathbb\{N\}\_1\backslash forall\; N\backslash leq\; n\backslash in\backslash mathbb\{N\}\_1,\; \backslash left\backslash frac\{\backslash \#\backslash left\backslash \{i\backslash in\backslash left\backslash \{1,2,\backslash dots,\; n\backslash right\backslash \}:\; f(i)\backslash in\; E\backslash right\backslash \}\}\{n\}P(E)\backslash right\; \backslash varepsilon$
($\backslash \#S$ denotes the number of elements in the finite set $S$.)
It can be shown that if $f$ is a pseudorandom number generator for the uniform distribution on $\backslash left(0,1\backslash right)$ and if $F$ is the CDF of some given probability distribution $P$, then $F^*\backslash circ\; f$ is a pseudorandom number generator for $P$, where $F^*:\backslash left(0,1\backslash right)\backslash rightarrow\backslash mathbb\{R\}$ is the percentile of $P$, i.e. $F^*(x):=\backslash inf\backslash left\backslash \{t\backslash in\backslash mathbb\{R\}:\; x\backslash leq\; F(t)\backslash right\backslash \}$. Intuitively, an arbitrary distribution can be simulated from a simulation of the standard uniform distribution.
Periodicity
A PRNG can be started from an arbitrary starting state using a seed state. It will always produce the same sequence thereafter when initialized with that state. The period of a PRNG is defined as the maximum over all starting states of the length of the repetitionfree prefix of the sequence. The period is bounded by the size of the state, measured in bits. However, since the length of the period potentially doubles with each bit of 'state' added, it is easy to build PRNGs with periods long enough for many practical applications.
If a PRNG's internal state contains n bits, its period can be no longer than 2^{n} results, and may be much shorter. For some PRNGs the period length can be calculated without walking through the whole period. Linear Feedback Shift Registers (LFSRs) are usually chosen to have periods of exactly 2^{n}−1. Linear congruential generators have periods that can be calculated by factoring. Mixes (no restrictions) have periods of about 2^{n/2} on average, usually after walking through a nonrepeating starting sequence. Mixes that are reversible (permutations) have periods of about 2^{n−1} on average, and the period will always include the original internal state.^{[4]} Although PRNGs will repeat their results after they reach the end of their period, a repeated result does not imply that the end of the period has been reached, since its internal state may be larger than its output; this is particularly obvious with PRNGs with a 1bit output.
Most pseudorandom generator 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 without knowing 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 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 (see below). The size of its period is an important factor in the cryptographic suitability of a PRNG, but not the only one.
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:
 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 amounts 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 of that period which relied on random selection or on Monte Carlo style simulations, or in other ways, is less reliable than it might have been as a result.^{[5]}
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 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 hundred times faster than reading numbers in from punched cards.
The middlesquare method has since been supplanted by more elaborate generators.
Mersenne twister
The 1997 invention of the Mersenne twister algorithm,^{[6]} avoids many of the problems with earlier generators. It 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 runs faster than other statistically reasonable generators. It is now increasingly becoming the random number generator of choice for statistical simulations and generative modeling.
SIMDoriented Fast Mersenne Twister (SFMT), a variant of Mersenne Twister, is 24 times faster even if it's not compiled with SIMD support.^{[7]}
The native Mersenne Twister is not considered suitable for use in all cryptographic applications. A variant of Mersenne Twister has been proposed as a cryptographic cipher.^{[8]}
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 such property cannot be proven, strong evidence may be provided by reducing the CSPRNG to a problem that is assumed to be hard, such as integer factorization.^{[9]} In general, years of review may be required before an algorithm can be certified as a CSPRNG.
Some classes of CSPRNGs include the following:
The NSA is reported to have inserted a backdoor into the NIST certified pseudorandom number generator Dual_EC_DRBG.^{[10]}
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.^{[11]} They are summarized here:
 K1 — A sequence of random numbers with a low probability of containing identical consecutive elements.
 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^{[11]} and NIST,^{[12]} 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.
Nonuniform generators
Main article: Pseudorandom number sampling
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 $F(b)$ of the target distribution $f(b)$:
 $F(b)=\backslash int\_\{\backslash infty\}^b\; f(b\text{'})\; db\text{'}$
Note that $0=F(\backslash infty)\backslash leq\; F(b)\; \backslash leq\; F(\backslash infty)=1$. Using a random number c from a uniform distribution as the probability density to "pass by", we get
 $F(b)=c$
so that
 $b=F^\{1\}(c)$
is a number randomly selected from distribution $f(b)$.
For example, the inverse of cumulative Gaussian distribution
$\backslash operatorname\{erf\}^\{1\}(x)$ with an ideal uniform PRNG with range (0, 1) as input $x$ 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 $\backslash operatorname\{erf\}^\{1\}(x)$ 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.
References
Bibliography
 Elaine Barker and , NIST SP80090A, January 2012
 Wolfgang Hörmann, Josef Leydold, Gerhard Derflinger (2004, 2011), Automatic Nonuniform Random Variate Generation, Berlin: SpringerVerlag
 Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. A definitive source of techniques for provably random sequences. ISBN 9780691025469
 Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. AddisonWesley, 1997. ISBN 0201896842. Chapter 3, pp. 1–193. Extensive coverage of statistical tests for nonrandomness.
 R. Matthews Maximally Periodic Reciprocals Bulletin of the Institute of Mathematics and its Applications 28 147148 1992
 , in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
 John von Neumann, "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.

 Richard P. Brent, Some longperiod random number generators using shifts and xors, ANZIAM Journal 2007; 48:C188–C202 Papercore link http://www.papercore.org/Brent2007
See also
External links
 Short video on random number generators explaining random seeds and middle squares method
 C library that includes a number of PRNG algorithms.
 C++ pseudorandom number generator library for sequential and parallel Monte Carlo simulations.
 C Random Number Test Suite.
 Java's "Math.random" method to generate numbers for random assignment and random sampling.
 crng: Randomnumber generators (RNGs) implemented as Python extension types coded in C.
 http://eeyore.wuwien.ac.at/src/ prng: A collection of algorithms for generating pseudorandom numbers as a library of C functions, released under the GPL
 strange attractors. This is a good practical example of issues in PRNGs and the variation possible in their implementation.
 Strange Attractors and TCP/IP Sequence Number Analysis  One Year Later  a followup article demonstrating some of the evolution of various PRNG algorithms over time.
 Embedded Systems by Eric Uner
 Analysis of the Linux Random Number Generator by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman
 Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators by Priv.Doz. Dr. Werner Schindler, Federal Office for Information Security
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.