Pseudorandom number generator

pseudo-random number generatorPRNGpseudorandompseudorandom number generationpseudorandom number generatorspseudo random number generatorpseudo-random number generatorspseudo-random numbersPseudorandom number sequencerandom number generator
This page is about commonly encountered characteristics of pseudorandom number generator algorithms.wikipedia
280 Related Articles

Random number generation

random number generatorrandom numberrandom numbers
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers.
Random number generators can be true hardware random-number generators (HRNG), which generate genuinely random numbers, or pseudo-random number generators (PRNG), which generate numbers that look random, but are actually deterministic, and can be reproduced if the state of the PRNG is known.

Cryptographically secure pseudorandom number generator

cryptographically secure pseudo-random number generatorCSPRNGcryptographic pseudorandom number generator
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.
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography.

Random seed

seedseededseed number
The PRNG-generated 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).
A random seed (or seed state, or just seed) is a number (or vector) used to initialize a pseudorandom number generator.

Mersenne Twister

Mersenne Twister MT19937MT19937
One well-known PRNG to avoid major problems and still run fairly quickly was the Mersenne Twister (discussed below), which was published in 1998.
The Mersenne Twister is a pseudorandom number generator (PRNG).

Linear congruential generator

linear congruentialLCG
, Java still relies on a linear congruential generator (LCG) for its PRNG; yet LCGs are of low quality—see further below.
The method represents one of the oldest and best-known pseudorandom number generator algorithms.

RANDU

An example was the RANDU random number algorithm used for decades on mainframe computers.
RANDU is a linear congruential pseudorandom number generator (LCG) of the Park–Miller type, which has been used since the 1960s.

Pseudorandomness

pseudorandompseudo-randompseudo-random numbers
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.
Pseudorandom number generators are widely used in such applications as computer modeling (e.g., Markov chains), statistics, experimental design, etc.

Hardware random number generator

true random number generatorentropy poolelectronic random event generators
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.
They are a more secure alternative to pseudorandom number generators (PRNGs), software programs commonly used in computers to generate "random" numbers.

Monte Carlo method

Monte CarloMonte Carlo simulationMonte Carlo methods
PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography.
Uses of Monte Carlo methods require large amounts of random numbers, and it was their use that spurred the development of pseudorandom number generators, which were far quicker to use than the tables of random numbers that had been previously used for statistical sampling.

Xorshift

3-shift linear feedback shift-registerxorshift+
In 2003, George Marsaglia introduced the family of xorshift generators, again based on a linear recurrence.
Xorshift random number generators, also called shift-register generators are a class of pseudorandom number generators that were discovered by George Marsaglia.

List of random number generators

List of pseudorandom number generators
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.
Whenever using a pseudorandom number generator, keep in mind John von Neumann's dictum "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."

Well equidistributed long-period linear

WELL
In 2006 the WELL family of generators was developed.
The Well Equidistributed Long-period Linear (WELL) is a family of pseudorandom number generators developed in 2006 by François Panneton, Pierre L'Ecuyer, and .

Procedural generation

procedurally generatedprocedurally-generatedrandomly generated
PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography.
Some games used pseudorandom number generators were often used with predefined seed values in order to generate very large game worlds that appeared to be premade.

Block cipher

block ciphersblockcipher
However, block ciphers may also feature as building blocks in other cryptographic protocols, such as universal hash functions and pseudo-random number generators.

Yarrow algorithm

Yarrow
The Yarrow algorithm is a family of cryptographic pseudorandom number generators (PRNG) devised by John Kelsey, Bruce Schneier, and Niels Ferguson and published in 1999.

Blum Blum Shub

BBSBlum Blum Shub generatorBlum-Blum-Shub
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.

Linear-feedback shift register

linear feedback shift registerLFSRgeneralised feedback shift register
A major advance in the construction of pseudorandom generators was the introduction of techniques based on linear recurrences on the two-element field; such generators are related to linear feedback shift registers.
LFSRs have long been used as pseudo-random number generators for use in stream ciphers (especially in military cryptography), due to the ease of construction from simple electromechanical or electronic circuits, long periods, and very uniformly distributed output streams.

Middle-square method

Middle Square Weyl Sequence PRNGmiddle square method
An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method.
In practice it is not a good method, since its period is usually very short and it has some severe weaknesses; repeated enough times, the middle-square method will either begin repeatedly generating the same number or cycle to a previous number in the sequence and loop indefinitely.

Ziggurat algorithm

Belonging to the class of rejection sampling algorithms, it relies on an underlying source of uniformly-distributed random numbers, typically from a pseudo-random number generator, as well as precomputed tables.

Applications of randomness

randomly
Mathematically, there are distinctions between randomization, pseudorandomization, and quasirandomization, as well as between random number generators and pseudorandom number generators.

Randomness

randomchancerandomly
The PRNG-generated 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).
Monte Carlo methods, which rely on random input (such as from random number generators or pseudorandom number generators), are important techniques in science, particularly in the field of computational science.

Microsoft CryptoAPI

Cryptographic Application Programming InterfaceCryptoAPICryptographic API
CNG also adds support for Dual_EC_DRBG, a pseudorandom number generator defined in NIST SP 800-90A that could expose the user to eavesdropping by the National Security Agency since it contains a kleptographic backdoor, unless the developer remembers to generate new base points with a different cryptographically secure pseudorandom number generator or a true random number generator and then publish the generated seed in order to remove the NSA backdoor.

National Institute of Standards and Technology

NISTNational Bureau of StandardsBureau of Standards
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.
The Guardian and The New York Times reported that NIST allowed the National Security Agency (NSA) to insert a cryptographically secure pseudorandom number generator called Dual EC DRBG into NIST standard SP 800-90 that had a kleptographic backdoor that the NSA can use to covertly predict the future outputs of this pseudorandom number generator thereby allowing the surreptitious decryption of data.

Naor–Reingold pseudorandom function

Naor-Reingold Pseudorandom FunctionNaor-Reingold constructionthere exist
There are other attacks that would be very bad for a pseudorandom number generator: the user expects to get random numbers from the output, so of course the stream should not be predictable, but even more, it should be indistinguishable from a random string.

Stream cipher

stream cypherstream ciphersstream
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.
* United States National Security Agency documents sometimes use the term combiner-type algorithms, referring to algorithms that use some function to combine a pseudorandom number generator (PRNG) with a plaintext stream.