FACTOID # 21: 15% of Army recruits from South Dakota are Native American, which is roughly the same percentage for female Army recruits in the state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Pseudorandom number generator

A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate 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. 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.g., of physical systems with the Monte Carlo method), and are central in the practice of cryptography. Image File history File links Broom_icon. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... Random redirects here. ... In computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. ... Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...


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. Recent instances of pseudo-random algorithms include Blum Blum Shub, Fortuna, and the Mersenne twister. In mathematics, the uniform distributions are simple probability distributions. ... Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. ... 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. ... Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ... Fortuna is a cryptographically secure pseudo-random number generator (PRNG) devised by Bruce Schneier and Niels Ferguson. ... The Mersenne twister is a pseudorandom number generator linked to CR developed in 1997 by Makoto Matsumoto ) and Takuji Nishimura )[1] that is based on a matrix linear recurrence over a finite binary field . ...


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."[1] As John von Neumann joked, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."[2] A combination of federal, state and private funds is providing $300 million for the construction of 13 facilities on ORNLs new main campus. ... For other persons named John Neumann, see John Neumann (disambiguation). ...

Contents

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 maximum length of the sequence before it begins to repeat is determined by the size of the state, measured in bits. 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. A random seed (or seed state, or just seed) is a number (or vector) used to initialize a pseudorandom number generator. ... This article is about the unit of information. ...


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. LFSRs are usually chosen to have periods of exactly 2n-1. Linear congruential generators have periods that can be calculated by factoring.[citation needed] 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.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. A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. ... Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. ... This article is about permutation, a mathematical concept. ...


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. 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. The design of cryptographically adequate PRNGs is extremely difficult. The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ... The operation of the keystream generator in A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... This article is about cryptography. ... This article is about algorithms for encryption and decryption. ...


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, but are certainly not limited to In natural science and signal processing, an artifact is any perceived distortion or other data error caused by the instrument of observation. ...

  • 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. ... For other uses, see Mainframe. ...


Early approaches

An early computer-based PRNG, suggested by John von Neumann in 1946, is known as the middle-square method. 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. For other persons named John Neumann, see John Neumann (disambiguation). ... Year 1946 (MCMXLVI) was a common year starting on Tuesday (link will display full 1946 calendar) of the Gregorian calendar. ... One iteration of the middle-square method, showing a six digit seed, which is then squared, and the resulting value has its middle six digits as the output value (and also as the next seed for the sequence). ...


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 ENIAC, short for Electronic Numerical Integrator And Computer,[1] was the first large-scale, electronic, digital computer capable of being reprogrammed to solve a full range of computing problems,[2] although earlier computers had been built with some of these properties. ... Punched cards (or Hollerith cards, or IBM cards), are pieces of stiff paper that contain digital information represented by the presence or absence of holes in predefined positions. ...


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. It has the colossal period of 219937-1 iterations (likely far more than the number of computations which 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. 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.[2] For the band, see 1997 (band). ... The Mersenne twister is a pseudorandom number generator linked to CR developed in 1997 by Makoto Matsumoto ) and Takuji Nishimura )[1] that is based on a matrix linear recurrence over a finite binary field . ... Equidistributed is a property of a bounded sequence of numbers. ... -1...


Although suitable for other purposes, the Mersenne twister is not considered suitable for use in cryptography. A variant has been proposed as a cryptographic cipher. [3] The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...


Cryptographically secure pseudorandom number generators

Main article: Cryptographically secure pseudorandom number generator

A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). 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. 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. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...


Some classes of CSPRNGs include the following:

The operation of the keystream generator in A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... Encryption Decryption In cryptography, a block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation. ... In cryptography, a block cipher operates on blocks of fixed length, often 64 or 128 bits. ... Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ... Microsoft Corporation, (NASDAQ: MSFT, HKSE: 4338) is a multinational computer technology corporation with global annual revenue of US$44. ... The Cryptographic Application Programming Interface (also known variously as CryptoAPI, Microsoft Cryptography API, or simply CAPI) is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography. ... CryptGenRandom is a random number generator function that is included in Microsofts Cryptographic Application Programming Interface. ... The Yarrow algorithm is a cryptographically secure pseudo-random number generator. ... Mac OS X (pronounced ) is a line of graphical operating systems developed, marketed, and sold by Apple Inc. ... FreeBSD is a Unix-like free operating system descended from AT&T UNIX via the Berkeley Software Distribution (BSD) branch through the 386BSD and 4. ... Fortuna is a cryptographically secure pseudo-random number generator (PRNG) devised by Bruce Schneier and Niels Ferguson. ...

BSI evaluation criteria

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

  • 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 Probability density function of Gaussian distribution (bell curve). ...

  • when using practical number representations the infinite "tails" of the distribution have to be truncated to finite values.
  • Repetitive recalculation of operatorname{erf}^{-1}(x) should be reduced by means such as ziggurat algorithm for faster generation.

Similar considerations apply to generating other non-uniform distributions such as Rayleigh and Poisson. The ziggurat algorithm generates normally-distributed random variables. ... 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 occurring in a fixed period of time if these events occur with a known average rate, and are independent of the time since the last event. ...


See also

A binary sequence (BS) is a sequence of bits, for , 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 is a computational or physical device designed to generate a sequence of elements (usually numbers), such that the sequence can be used as a random one. ... The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. ... The following pseudorandom number generators are recommended for use in simulation. ... Random redirects here. ...

Notes

  1. ^ Peterson, Ivars. 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. 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.

Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... As a non-regulatory agency of the United States Department of Commerce’s Technology Administration, the National Institute of Standards (NIST) develops and promotes measurement, standards, and technology to enhance productivity, facilitate trade, and improve the quality of life. ...

External links

GPL redirects here. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... GPL redirects here. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... The Internet protocol suite is the set of communications protocols that implement the protocol stack on which the Internet runs. ... The Transmission Control Protocol (TCP) is one of the core protocols of the Internet protocol suite, often simply referred to as TCP/IP. Using TCP, applications on networked hosts can create connections to one another, over which they can exchange streams of data using Stream Sockets. ... An operating system (OS) is the software that manages the sharing of the resources of a computer and provides programmers with an interface used to access those resources. ... In the study of dynamical systems, an attractor is a set, curve, or space to which a system irreversibly evolves, if left undisturbed. ... What is an Embedded System? Electronic devices that incorporate a computer(usually a microprocessor) within their implementation. ...

  Results from FactBites:
 
Encyclopedia4U - Pseudorandom number generator - Encyclopedia Article (777 words)
A pseudorandom number generator (PRNG) is an algorithm which when run generates a sequence of numbers, the elements of which are approximately independent.
The outputs of pseudorandom number generators are not random---they only approximate some of the properties of random numbers.
Most stream ciphers work by generating a pseudorandom stream of bits that are XORed with the message; this stream can be used as a good CSPRNG (thought not always: see RC4).
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m