List of random number generators

Last updated

Random number generators are important in many kinds of technical applications, including physics, engineering or mathematical computer studies (e.g., Monte Carlo simulations), cryptography and gambling (on game servers).

Contents

This list includes many common types, regardless of quality or applicability to a given use case.

Pseudorandom number generators (PRNGs)

The following algorithms are pseudorandom number generators.

GeneratorDateFirst proponentsReferencesNotes
Middle-square method 1946J. von Neumann [1] In its original form, it is of poor quality and of historical interest only.
Lehmer generator 1951D. H. Lehmer [2] One of the very earliest and most influential designs.
Linear congruential generator (LCG)1958W. E. Thomson; A. Rotenberg [3] [4] A generalisation of the Lehmer generator and historically the most influential and studied generator.
Lagged Fibonacci generator (LFG)1958G. J. Mitchell and D. P. Moore [5]
Linear-feedback shift register (LFSR)1965R. C. Tausworthe [6] A hugely influential design. Also called Tausworthe generators.
Wichmann–Hill generator 1982B. A. Wichmann and D. I. Hill [7] A combination of three small LCGs, suited to 16-bit CPUs. Widely used in many programs, e.g. it is used in Excel 2003 and later versions for the Excel function RAND [8] and it was the default generator in the language Python up to version 2.2. [9]
Rule 30 1983S. Wolfram [10] Based on cellular automata.
Inversive congruential generator (ICG)1986J. Eichenauer and J. Lehn [11]
Blum Blum Shub 1986M. Blum, L. Blum and M. Shub [12] Blum-Blum-Shub is a PRNG algorithm that is considered cryptographically secure. Its base is based on prime numbers.
Park-Miller generator 1988S. K. Park and K. W. Miller [13] A specific implementation of a Lehmer generator, widely used because it is included in C++ as the function minstd_rand0 from C++11 onwards. [14]
ACORN generator 1989 (discovered 1984)R. S. Wikramaratna [15] [16] The Additive Congruential Random Number generator.

Simple to implement, fast, but not widely known. With appropriate initialisations, passes all current empirical test suites, and is formally proven to converge. Easy to extend for arbitrary period length and improved statistical performance over higher dimensions and with higher precision.

MIXMAX generator 1991G. K. Savvidy and N. G. Ter-Arutyunyan-Savvidy [17] It is a member of the class of matrix linear congruential generator, a generalisation of LCG. The rationale behind the MIXMAX family of generators relies on results from ergodic theory and classical mechanics.
Add-with-carry (AWC)1991G. Marsaglia and A. Zaman [18] A modification of Lagged-Fibonacci generators.
Subtract-with-borrow (SWB)1991G. Marsaglia and A. Zaman [18] A modification of Lagged-Fibonacci generators. A SWB generator is the basis for the RANLUX generator, [19] widely used e.g. for particle physics simulations.
Maximally periodic reciprocals 1992R. A. J. Matthews [20] A method with roots in number theory, although never used in practical applications.
KISS 1993G. Marsaglia [21] Prototypical example of a combination generator.
Multiply-with-carry (MWC)1994G. Marsaglia; C. Koç [22] [23]
Complementary-multiply-with-carry (CMWC)1997R. Couture and P. L’Ecuyer [24]
Mersenne Twister (MT)1998M. Matsumoto and T. Nishimura [25] Closely related with LFSRs. In its MT19937 implementation is probably the most commonly used modern PRNG. Default generator in R and the Python language starting from version 2.3.
Xorshift 2003G. Marsaglia [26] It is a very fast sub-type of LFSR generators. Marsaglia also suggested as an improvement the xorwow generator, in which the output of a xorshift generator is added with a Weyl sequence. The xorwow generator is the default generator in the CURAND library of the nVidia CUDA application programming interface for graphics processing units.
Well equidistributed long-period linear (WELL)2006F. Panneton, P. L'Ecuyer and M. Matsumoto [27] A LFSR closely related with Mersenne Twister, aiming at remedying some of its shortcomings.
A small noncryptographic PRNG (JSF)2007Bob Jenkins [28]
Advanced Randomization System (ARS) 2011J. Salmon, M. Moraes, R. Dror and D. Shaw [29] A simplified version of the AES block cipher, leading to very fast performance on systems supporting the AES-NI.
Threefry 2011J. Salmon, M. Moraes, R. Dror and D. Shaw [29] A simplified version of the Threefish block cipher, suitable for GPU implementations.
Philox 2011J. Salmon, M. Moraes, R. Dror and D. Shaw [29] A simplification and modification of the block cipher Threefish with the addition of an S-box.
WELLDOC2013L. Balkova, M. Bucci, A. de Luca, J. Hladky, S. Puzynina [30] Aperiodic pseudorandom number generators based on infinite words technique.
SplitMix2014G. L. Steele, D. Lea and C. H. Flood [31] Based upon the final mixing function of MurmurHash3. Included in Java Development Kit 8 and above.
Permuted Congruential Generator (PCG)2014M. E. O'Neill [32] A modification of LCG.
Random Cycle Bit Generator (RCB)2016R. Cookman [33] RCB is described as a bit pattern generator made to overcome some of the shortcomings with Mersenne Twister and short periods/bit length restriction of shift/modulo generators.
Middle-Square Weyl Sequence RNG (see also middle-square method)2017B. Widynski [34] [35] A variation on John von Neumann's original middle-square method, this generator may be the fastest RNG that passes all the statistical tests.
Xoroshiro128+ 2018D. Blackman, S. Vigna [36] A modification of Marsaglia's Xorshift generators, one of the fastest generators on modern 64-bit CPUs. Related generators include xoroshiro128**, xoshiro256+ and xoshiro256**.
64-bit MELG (MELG-64)2018S. Harase, T. Kimoto [37] An implementation of 64-bit maximally equidistributed F2-linear generators with Mersenne prime period.
Squares RNG 2020B. Widynski [38] A counter-based version of Middle-Square Weyl Sequence RNG. Similar to Philox in design but significantly faster.

Cryptographic algorithms

Cipher algorithms and cryptographic hashes can be used as very high-quality pseudorandom number generators. However, generally they are considerably slower (typically by a factor 2–10) than fast, non-cryptographic random number generators.

These include:

A few cryptographically secure pseudorandom number generators do not rely on cipher algorithms but try to link mathematically the difficulty of distinguishing their output from a `true' random stream to a computationally difficult problem. These approaches are theoretically important but are too slow to be practical in most applications. They include:

Random number generators that use external entropy

These approaches combine a pseudo-random number generator (often in the form of a block or stream cipher) with an external source of randomness (e.g., mouse movements, delay between keyboard presses etc.).

See also

Related Research Articles

A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Simply put, the problem is that many of the sources of randomness available to humans rely on physical processes not readily available to computer programs.

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. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. 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.

<span class="mw-page-title-main">Linear congruential generator</span> Algorithm for generating pseudo-randomized numbers

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.

The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto and Takuji Nishimura. Its name derives from the fact that its period length is chosen to be a Mersenne prime.

<span class="mw-page-title-main">Hardware random number generator</span> Cryptographic device

In computing, a hardware random number generator (HRNG), true random number generator (TRNG), non-deterministic random bit generator (NRBG), or physical random number generator is a device that generates random numbers from a physical process capable of producing entropy, unlike the pseudorandom number generator that utilizes a deterministic algorithm and non-physical nondeterministic random bit generators that do not include hardware dedicated to generation of entropy.

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. It is also loosely known as a cryptographic random number generator (CRNG).

<span class="mw-page-title-main">Manuel Blum</span> Venezuelan computer scientist

Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

Fortuna is a cryptographically secure pseudorandom number generator (CS-PRNG) devised by Bruce Schneier and Niels Ferguson and published in 2003. It is named after Fortuna, the Roman goddess of chance. FreeBSD uses Fortuna for /dev/random and /dev/urandom is symbolically linked to it since FreeBSD 11. Apple OSes have switched to Fortuna since 2020 Q1.

In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class can distinguish between the output of the generator and the uniform distribution. The random seed itself is typically a short binary string drawn from the uniform distribution.

<span class="mw-page-title-main">Russell Impagliazzo</span> American computer scientist

Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.

<span class="mw-page-title-main">Random number generation</span> Producing a sequence that cannot be predicted better than by random chance

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but impossible to foresee. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

<span class="mw-page-title-main">Michael Luby</span> Information theorist and cryptographer

Michael George Luby is a mathematician and computer scientist, CEO of BitRipple, senior research scientist at the International Computer Science Institute (ICSI), former VP Technology at Qualcomm, co-founder and former chief technology officer of Digital Fountain. In coding theory he is known for leading the invention of the Tornado codes and the LT codes. In cryptography he is known for his contributions showing that any one-way function can be used as the basis for private cryptography, and for his analysis, in collaboration with Charles Rackoff, of the Feistel cipher construction. His distributed algorithm to find a maximal independent set in a computer network has also been influential.

The Lehmer random number generator, sometimes also referred to as the Park–Miller random number generator, is a type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. The general formula is

<span class="mw-page-title-main">Xorshift</span> Class of pseudorandom number generators

Xorshift random number generators, also called shift-register generators, are a class of pseudorandom number generators that were invented by George Marsaglia. They are a subset of linear-feedback shift registers (LFSRs) which allow a particularly efficient implementation in software without the excessive use of sparse polynomials. They generate the next number in their sequence by repeatedly taking the exclusive or of a number with a bit-shifted version of itself. This makes execution extremely efficient on modern computer architectures, but it does not benefit efficiency in a hardware implementation. Like all LFSRs, the parameters have to be chosen very carefully in order to achieve a long period.

The Blum–Micali algorithm is a cryptographically secure pseudorandom number generator. The algorithm gets its security from the difficulty of computing discrete logarithms.

In sequence design, a Feedback with Carry Shift Register is the arithmetic or with carry analog of a linear-feedback shift register (LFSR). If is an integer, then an N-ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer . The state change operation is determined by a set of coefficients and is defined as follows: compute . Express s as with in . Then the new state is . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in .

TestU01 is a software library, implemented in the ANSI C language, that offers a collection of utilities for the empirical randomness testing of random number generators (RNGs). The library was first introduced in 2007 by Pierre L’Ecuyer and Richard Simard of the Université de Montréal.

A counter-based random number generation is a kind of pseudorandom number generator that uses only an integer counter as its internal state. They are generally used for generating pseudorandom numbers for large parallel computations.

KISS (Keep it Simple Stupid) is a family of pseudorandom number generators introduced by George Marsaglia. Starting from 1998 Marsaglia posted on various newsgroups including sci.math, comp.lang.c, comp.lang.fortran and sci.stat.math several versions of the generators. All KISS generators combine three or four independent random number generators with a view to improving the quality of randomness. KISS generators produce 32-bit or 64-bit random integers, from which random floating-point numbers can be constructed if desired. The original 1993 generator is based on the combination of a linear congruential generator and of two linear feedback shift-register generators. It has a period 295, good speed and good statistical properties; however, it fails the LinearComplexity test in the Crush and BigCrush tests of the TestU01 suite. A newer version from 1999 is based on a linear congruential generator, a 3-shift linear feedback shift-register and two multiply-with-carry generators. It is 10–20% slower than the 1993 version but has a larger period 2123 and passes all tests in TestU01. In 2009 Marsaglia presented a version based on 64-bit integers (appropriate for 64-bit processors) which combines a multiply-with-carry generator, a Xorshift generator and a linear congruential generator. It has a period of around 2250 (around 1075).

References

  1. ↑ Some of von Neumann's 1949 papers were printed only in 1951. 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, vol. 12 (Washington, D.C.: U.S. Government Printing Office, 1951): pp. 36–38.
  2. ↑ Lehmer, Derrick H. (1951). "Mathematical methods in large-scale computing units". Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery: 141–146.
  3. ↑ Thomson, W. E. (1958). "A Modified Congruence Method of Generating Pseudo-random Numbers". The Computer Journal. 1 (2): 83. doi: 10.1093/comjnl/1.2.83 .
  4. ↑ Rotenberg, A. (1960). "A New Pseudo-Random Number Generator". Journal of the ACM. 7 (1): 75–77. doi: 10.1145/321008.321019 . S2CID   16770825.
  5. ↑ D. E. Knuth, The Art of Computer Programming, Vol. 2 Seminumerical Algorithms, 3rd ed., Addison Wesley Longman (1998); See pag. 27.
  6. ↑ Tausworthe, R. C. (1965). "Random Numbers Generated by Linear Recurrence Modulo Two" (PDF). Mathematics of Computation. 19 (90): 201–209. doi: 10.1090/S0025-5718-1965-0184406-1 .
  7. ↑ Wichmann, Brian A.; Hill, David I. (1982). "Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator". Journal of the Royal Statistical Society. Series C (Applied Statistics). 31 (2): 188–190. doi:10.2307/2347988. JSTOR   2347988.
  8. ↑ "Microsoft Support - Description of the RAND function in Excel". Apr 17, 2018.
  9. ↑ "Documentation » The Python Standard Library » 9. Numeric and Mathematical Modules » 9.6. random — Generate pseudo-random numbers".
  10. ↑ Wolfram, S. (1983). "Statistical mechanics of cellular automata". Rev. Mod. Phys. 55 (3): 601–644. Bibcode:1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601.
  11. ↑ Eichenauer, Jürgen; Lehn, Jürgen (1986). "A nonlinear congruential pseudorandom number generator". Statistische Hefte. 27: 315–326. doi:10.1007/BF02932576. S2CID   122052399.
  12. ↑ Blum, L.; Blum, M.; Shub, M. (1986-05-01). "A Simple Unpredictable Pseudo-Random Number Generator". SIAM Journal on Computing. 15 (2): 364–383. doi:10.1137/0215025. ISSN   0097-5397.
  13. ↑ Park, Stephen K.; Miller, Keith W. (1988). "Random Number Generators: Good Ones Are Hard To Find" (PDF). Communications of the ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042. S2CID   207575300.
  14. ↑ "Pseudo-random number generation". cppreference.com. Retrieved 14 November 2021.
  15. ↑ Wikramaratna, R. S. (1989). "ACORN — A new method for generating sequences of uniformly distributed Pseudo-random Numbers". Journal of Computational Physics. 83 (1): 16–31. Bibcode:1989JCoPh..83...16W. doi:10.1016/0021-9991(89)90221-0.
  16. ↑ Wikramaratna, R.S. Theoretical and empirical convergence results for additive congruential random number generators, Journal of Computational and Applied Mathematics (2009), doi : 10.1016/j.cam.2009.10.015
  17. ↑ Savvidy, G.K; Ter-Arutyunyan-Savvidy, N.G (1991). "On the Monte Carlo simulation of physical systems". Journal of Computational Physics . 97 (2): 566. Bibcode:1991JCoPh..97..566S. doi:10.1016/0021-9991(91)90015-D.
  18. 1 2 George, Marsaglia; Zaman, Arif (1991). "A new class of random number generators". Annals of Applied Probability. 1 (3): 462–480. doi: 10.1214/aoap/1177005878 .
  19. ↑ Martin, Lüscher (1994). "A portable high-quality random number generator for lattice field theory simulations". Computer Physics Communications. 79 (1): 100–110. arXiv: hep-lat/9309020 . Bibcode:1994CoPhC..79..100L. doi:10.1016/0010-4655(94)90232-1. S2CID   17608961.
  20. ↑ Matthews, Robert A. J. (1992). "Maximally periodic reciprocals". Bull. Inst. Math. Appl. 28: 147–148.
  21. ↑ Marsaglia, George; Zaman, Arif (1993). "The KISS generator". Technical Report, Department of Statistics, Florida State University, Tallahassee, FL, USA.
  22. ↑ Post by George Marsaglia on the newsgroup sci.stat.math dated 1 August 2018 with title 'Yet another RNG'.
  23. ↑ Koç, Cemal (1995). "Recurring-with-Carry Sequences". Journal of Applied Probability. 32 (4): 966–971. doi:10.2307/3215210. JSTOR   3215210. S2CID   123798320.
  24. ↑ Couture, Raymond; L'Ecuyer, Pierre (1997). "Distribution properties of multiply-with-carry random number generators" (PDF). Mathematics of Computation. 66 Number. 218 (218): 591–607. Bibcode:1997MaCom..66..591C. doi: 10.1090/S0025-5718-97-00827-2 .
  25. ↑ Matsumoto, M.; Nishimura, T. (1998). "MersenneTwister: A623-dimensionally Equidistributed Uniform Pseudo-Random Number Generator". ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX   10.1.1.215.1141 . doi:10.1145/272991.272995. S2CID   3332028.
  26. ↑ Marsaglia, George (July 2003). "Xorshift RNGs". Journal of Statistical Software . 8 (14). doi: 10.18637/jss.v008.i14 .
  27. ↑ Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Pierre (March 2006). "Improved long-period generators based on linear recurrences modulo 2" (PDF). ACM Transactions on Mathematical Software. 32 (1): 1–16. CiteSeerX   10.1.1.73.5499 . doi:10.1145/1132973.1132974. S2CID   7368302.
  28. ↑ Jenkins, Bob (2009). "A small noncryptographic PRNG".
  29. 1 2 3 Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Parallel random numbers: as easy as 1, 2, 3". Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16. doi:10.1145/2063384.2063405.
  30. ↑ Balkova, Lubomira; Bucci, Michelangelo; De Luca, Alessandro; Hladky, Jiri; Puzynina, Svetlana (September 2016). "Aperiodic pseudorandom number generators based on infinite words". Theoretical Computer Science. 647: 85–100. arXiv: 1311.6002 . doi:10.1016/j.tcs.2016.07.042. S2CID   2175443.
  31. ↑ Steele, Guy L. Jr.; Lea, Doug; Flood, Christine H. (2014). "Fast splittable pseudorandom number generators" (PDF). OOPSLA '14 Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications.
  32. ↑ O'Neill, Melissa E. (2014). "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation" (PDF). Technical Report.
  33. ↑ Cookman, Richard (2016). "random cycle bit generator (rcb_generator)". Technical Report.
  34. ↑ Widynski, Bernard (2017). "Middle-Square Weyl Sequence RNG". arXiv: 1704.00358 [cs.CR].
  35. ↑ Kneusel, Ron (2018). Random Numbers and Computers (1 ed.). Springer. pp. 13–14. ISBN   9783319776972.
  36. ↑ Blackman, David; Vigna, Sebastiano (2018). "Scrambled Linear Pseudorandom Generators". arXiv: 1805.01407 [cs.DS].
  37. ↑ Harase, S.; Kimoto, T. (2018). "Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period". ACM Transactions on Mathematical Software. 44 (3): 30:1–30:11. arXiv: 1505.06582 . doi:10.1145/3159444. S2CID   14923086.
  38. ↑ Widynski, Bernard (2020). "Squares: A Fast Counter-Based RNG". arXiv: 2004.06278 [cs.DS].
  39. ↑ True Random Number Generator using Corona Discharge: Indian Patent Office. Patent Application Number: 201821026766
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.