A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation 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. Randomness is a lack of order Purpose, cause, or predictability Although sequences that are closer to truly random can be generated using hardware random number generators, pseudo-random numbers are important in practice for simulations (e. In Computing, a hardware random number generator is an apparatus that generates Random numbers from a physical process g. , of physical systems with the Monte Carlo method), and are central in the practice of cryptography. Monte Carlo methods are a class of Computational Algorithms that rely on repeated Random sampling to compute their results Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write"

Most pseudo-random generator algorithms produce sequences which are uniformly distributed by any of several tests. Common classes of these algorithms are linear congruential generators, lagged Fibonacci generators, linear feedback shift registers and generalised feedback shift registers. A linear congruential generator ( LCG) represent one of the oldest and best-known Pseudorandom number generator Algorithms The theory behind them is easy A Lagged Fibonacci generator (LFG is an example of a Pseudorandom number generator. A linear feedback shift register (LFSR is a Shift register whose input bit is a linear function of its previous state Recent instances of pseudo-random algorithms include Blum Blum Shub, Fortuna, and the Mersenne twister. Blum Blum Shub ( BBS) is a Pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et Fortuna is a Cryptographically secure pseudorandom number generator (PRNG devised by Bruce Schneier and Niels Ferguson. The Mersenne twister is a Pseudorandom number generator developed in 1997 by and that is based on a Matrix linear recurrence over a finite binary

Careful mathematical analysis is required to have any confidence a PRNG generates numbers that are sufficiently "random" to suit the intended use. 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. Oak Ridge National Laboratory ( ORNL) is a multiprogram science and technology National laboratory managed for the United States Department of Energy by "[1] As John von Neumann joked, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. "[2]

Periodicity

A PRNG can be started from an arbitrary starting state, using a seed state. A random seed (or seed state, or just seed) is a Number (or vector) used to initialize a Pseudorandom number generator. It will always produce the same sequence thereafter when initialized with that state. The maximum length of the sequence before it begins to repeat is determined by the size of the state, measured in bits. A bit is a binary digit, taking a value of either 0 or 1 Binary digits are a basic unit of Information storage and communication However, since the length of the maximum period potentially doubles with each bit of 'state' added, it is easy to build PRNGs with periods long enough for any practical application.

If a PRNG's internal state contains n bits, its period can be no longer than 2n results. 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 2n-1. A linear feedback shift register (LFSR is a Shift register whose input bit is a linear function of its previous state Linear congruential generators have periods that can be calculated by factoring. A linear congruential generator ( LCG) represent one of the oldest and best-known Pseudorandom number generator Algorithms The theory behind them is easy Mixes (no restrictions) have periods of about 2n/2 on average, usually after walking through a nonrepeating starting sequence. Mixes that are reversible (permutations) have periods of about 2n-1 on average, and the period will always include the original internal state (e. In several fields of Mathematics the term permutation is used with different but closely related meanings g. [1]). 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.

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 without knowing the algorithm(s) used and the state with which it was initialized. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" 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 a 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. In Cryptography, a stream cipher is a symmetric key Cipher where plaintext bits are combined with a Pseudorandom cipher bit stream ( Keystream In Cryptography, plaintext is the information which the sender wishes to transmit to the receiver(s The design of cryptographically adequate PRNGs is extremely difficult.

Problems with deterministic generators

In practice, the output from many common PRNGs exhibit artifacts which cause them to fail statistical pattern detection tests. In Natural science and Signal processing, an artifact is any perceived Distortion or other Data error caused by the instrument of observation These include, but are certainly not limited to

• Shorter than expected periods for some seed states; such seed states may be called 'weak' in this context
• Lack of uniformity of distribution
• 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 to absurdly obvious. The RANDU random number algorithm used for decades on mainframe computers was seriously flawed, and much research work of that period is less reliable than it might have been, as a result. RANDU is an infamous linear congruential Pseudorandom number generator which has been used since the 1960s Mainframes (often colloquially referred to as Big Iron) are Computers used mainly by large organizations for critical applications typically bulk data

Early approaches

An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method. Year 1946 ( MCMXLVI) was a Common year starting on Tuesday (link will display full 1946 calendar of the Gregorian calendar. In Mathematics, the Middle-square method is a method of generating Pseudorandom numbers In practice it is not a good method since its period is usually very It is very simple: take any number, square it, remove the middle digits of the resulting number as your "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 8-digit number being the square of a 4-digit 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 two hundred times faster than reading numbers in from punch cards. ENIAC, short for Electronic Numerical Integrator And Computer, was the first general-purpose electronic Computer.

The middle-square method has been supplanted by more elaborate generators.

Mersenne twister

The 1997 invention of the Mersenne twister algorithm, by Makoto Matsumoto and Takuji Nishimura, avoids many of the problems with earlier generators. Year 1997 ( MCMXCVII) was a Common year starting on Wednesday (link will display full 1997 Gregorian calendar The Mersenne twister is a Pseudorandom number generator developed in 1997 by and that is based on a Matrix linear recurrence over a finite binary It has the colossal period of 219937-1 iterations (likely far more than the number of computations that can be performed within 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 other statistically reasonable generators. In Mathematics, a bounded sequence { s 1 s 2 s 3 …} of Real numbers is said to be equidistributed It is now increasingly becoming the random number generator of choice for statistical simulations and generative modeling. SFMT, SIMD-oriented Fast Mersenne Twister, a variant of Mersenne twister, is faster even if it's not compiled with SIMD support. In Computing, SIMD ( S ingle I nstruction M ultiple D ata is a technique employed to achieve data level parallelism as in a Vector [2]

Although suitable for other purposes, the Mersenne twister is not considered suitable for use in cryptography. Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" A variant has been proposed as a cryptographic cipher. [3]

Cryptographically secure pseudorandom number generators

A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). A cryptographically secure pseudo-random number generator ( CSPRNG) is a Pseudo-random number generator (PRNG with properties that make it suitable for use in Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write" The difference between a PRNG and a CSPRNG is not simple: a CSPRNG must meet certain design principles and be resistant to known attacks. Years of review are required before such an algorithm can be certified and it is still possible attacks will be discovered in the future.

Some classes of CSPRNGs include the following:

• Stream ciphers
• block ciphers running in counter or output feedback mode. In Cryptography, a stream cipher is a symmetric key Cipher where plaintext bits are combined with a Pseudorandom cipher bit stream ( Keystream In Cryptography, a block cipher is a symmetric key Cipher which operates on fixed-length groups of Bits termed blocks, with an
• Special designs with a security proof. For example Blum Blum Shub has a strong security proof, although the proof is conditional and requires that some internal values remain secret from any attacker. Blum Blum Shub ( BBS) is a Pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et Moreover, Blum Blum Shub is too slow for many applications.
• 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. Microsoft Corporation is an American multinational Computer technology Corporation, which rose to dominate the Home computer The Cryptographic Application Programming Interface (also known variously as CryptoAPI, Microsoft Cryptography API, or simply CAPI) is an Application CryptGenRandom is a crytographically secure pseudorandom number generator function that is included in Microsoft 's Cryptographic Application Programming Interface The Yarrow algorithm is a Cryptographically secure pseudorandom number generator. Mac OS X (mæk oʊ ɛs tɛn is a line of computer Operating systems developed marketed and sold by Apple Inc, the latest of which is pre-loaded on all currently FreeBSD is a Unix-like free Operating system descended from AT&T UNIX via the Berkeley Software Distribution (BSD branch through Fortuna is a Cryptographically secure pseudorandom number generator (PRNG devised by Bruce Schneier and Niels Ferguson.
• Combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any non-randomness.

BSI evaluation criteria

The German Federal Office for Information Security (BSI) has established a four-part criteria for quality of deterministic random number generators. The Bundesamt für Sicherheit in der Informationstechnik (abbreviated BSI - in English Federal Office for Information Security) is the German government They are summarized here:

• K1 -- A sequence of random numbers with a high probability of containing no 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 chi-squared 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 BSI2 (AIS 20, v. 1, 1999) and FIPS (140-1, 1994), 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 one-half; 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 sub-sequence, 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 K4 standard are really acceptable.

Non-uniform generators

Non-uniform probability distributions can be generated using a uniform distribution PRNG and a non-linear function. For example the inverse of cumulative Gaussian distribution $\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. The normal distribution, also called the Gaussian distribution, is an important family of Continuous probability distributions applicable in many fields
• Repetitive recalculation of $\operatorname{erf}^{-1}(x)$ should be reduced by means such as ziggurat algorithm for faster generation. The ziggurat algorithm is an algorithm to generate random numbers from a non- uniform distribution.

Similar considerations apply to generating other non-uniform distributions such as Rayleigh and Poisson. In Probability theory and Statistics, the Rayleigh distribution is a Continuous Probability distribution. In Probability theory and Statistics, the Poisson distribution is a Discrete probability distribution that expresses the probability of a number of events

Notes

1. ^ Peterson, Ivars. A Binary sequence (BS is a sequence of N bits a_j for j=01N-1 i A randomized algorithm or probabilistic algorithm is an Algorithm which employs a degree of randomness as part of its logic A random number generator (often abbreviated as RNG is a computational or physical device designed to generate a sequence of Numbers or symbols that lack any The security of Cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others Computer Random number generators are important in Mathematics, Cryptography and Gambling. Randomness is a lack of order Purpose, cause, or predictability 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

• Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. A definitive source of techniques for provably random sequences.
• Donald Knuth. Donald Ervin Knuth (kəˈnuːθ (born 10 January 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3, pp. 1–193. Extensive coverage of statistical tests for non-randomness.
• R. Matthews Maximally Periodic Reciprocals Bulletin of the Institute of Mathematics and its Applications 28 147-148 1992
• J. Viega, Practical Random Number Generation in Software, 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): 36-38.
• NIST Recommendation for Random Number Generation Using Deterministic Random Bit Generators
• Luc Devroye Non-Uniform Random Variate Generation, Springer-Verlag, New York, 1986.