[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.
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.
"[3] In practice, the output from many common PRNGs exhibit artifacts that cause them to fail statistical pattern-detection tests.
These include: 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.
In many fields, research work prior to the 21st century that relied on random selection or on Monte Carlo simulations, or in other ways relied on PRNGs, were much less reliable than ideal as a result of using poor-quality PRNGs.
[4] Even today, caution is sometimes required, as illustrated by the following warning in the International Encyclopedia of Statistical Science (2010).
Check the default RNG of your favorite software and be ready to replace it if needed.
Perhaps amazingly, it remains as relevant today as it was 40 years ago.As an illustration, consider the widely used programming language Java.
Up until 2020, Java still relied on a linear congruential generator (LCG) for its PRNG,[6][7] which is of low quality (see further below).
One well-known PRNG to avoid major problems and still run fairly quickly is the Mersenne Twister (discussed below), which was published in 1998.
Other higher-quality PRNGs, both in terms of computational and statistical performance, were developed before and after this date; these can be identified in the List of pseudorandom number generators.
In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised linear congruential generators.
The Mersenne Twister has a period of 219 937 − 1 iterations (≈ 4.3×106001), is proven to be equidistributed in (up to) 623 dimensions (for 32-bit 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.
They are generally used for generating pseudorandom numbers for large parallel computations, such as over GPU or CPU clusters.
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 to the CSPRNG from a problem that is assumed to be hard, such as integer factorization.
[16] In general, years of review may be required before an algorithm can be certified as a CSPRNG.
Some classes of CSPRNGs include the following: 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.
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.
[21] 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 or-ing 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 German Federal Office for Information Security (German: Bundesamt für Sicherheit in der Informationstechnik, BSI) has established four criteria for quality of deterministic random number generators.
An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method.
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.
A recent innovation is to combine the middle square with a Weyl sequence.