Editing Pseudorandom number generator

{{Short description|Algorithm that generates an approximation of a random number sequence}}
{{Hatnote|This page is about commonly encountered characteristics of pseudorandom number generator algorithms. For the formal concept in theoretical computer science, see [[Pseudorandom generator]].}}
A '''pseudorandom number generator''' ('''PRNG'''), also known as a '''deterministic random bit generator''' ('''DRBG'''),<ref>{{cite journal|last=Barker|first=Elaine|title=Recommendation for Key Management|url=http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf|journal=NIST Special Publication 800-57|publisher=[[NIST]]|access-date=19 August 2013|author2=Barker, William |author3=Burr, William |author4=Polk, William |author5= Smid, Miles |date=July 2012|doi=10.6028/NIST.SP.800-57p1r3 }}</ref> is  an [[algorithm]] for generating a sequence of numbers whose properties approximate the properties of sequences of [[random number generation|random numbers]]. The PRNG-generated sequence is not truly [[random]], because it is completely determined by an initial value, called the PRNG's ''[[random seed|seed]]'' (which may include truly random values). Although sequences that are closer to truly random can be generated using [[hardware random number generator]]s, '''''pseudorandom number generators''''' are important in practice for their speed in number generation and their reproducibility.<ref>{{Cite web|title = Pseudorandom number generators|url = https://www.khanacademy.org/computing/computer-science/cryptography/crypt/v/random-vs-pseudorandom-number-generators|website = Khan Academy|access-date = 2016-01-11}}</ref>

PRNGs are central in applications such as [[simulation]]s (e.g. for the [[Monte Carlo method]]), [[electronic game]]s (e.g. for [[procedural generation]]), and [[cryptography]]. Cryptographic applications require the output not to be predictable from earlier outputs, and more [[cryptographically-secure pseudorandom number generator|elaborate algorithms]], which do not inherit the linearity of simpler PRNGs, are needed.

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. [[John von Neumann]] cautioned about the misinterpretation of a PRNG as a truly random generator, joking that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."<ref>{{cite journal|last=Von Neumann|first=John|title=Various techniques used in connection with random digits|journal=National Bureau of Standards Applied Mathematics Series|year=1951|volume=12|pages=36–38|url=https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf|archive-url=http://web.archive.org/web/20221128083015/https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf |archive-date=28 November 2022 }}</ref>

=={{Anchor|Potential problems with deterministic generators}}Potential issues==
In practice, the output from many common PRNGs exhibit [[artifact (error)|artifact]]s that cause them to fail statistical pattern-detection tests. These include:

* Shorter-than-expected periods for some seed states (such seed states may be called "weak" in this context);
* Lack of uniformity of distribution for large quantities of generated numbers;
* Correlation of successive values;
* Poor dimensional distribution of the output sequence;
* Distances between where certain values occur are distributed differently from those in a random sequence distribution.

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 computer]]s. It was seriously flawed, but its inadequacy went undetected for a very long time.

In many fields, research work prior to the 21st century that relied on random selection or on [[Monte Carlo method|Monte Carlo]] simulations, or in other ways relied on PRNGs, were much less reliable than ideal as a result of using poor-quality PRNGs.<ref>Press et al. (2007), chap.7</ref> Even today, caution is sometimes required, as illustrated by the following warning in the ''[[International Encyclopedia of Statistical Science]]'' (2010).<ref>{{cite book |last=L'Ecuyer |first=Pierre |contribution=Uniform random number generators |page=1629 |title=[[International Encyclopedia of Statistical Science]] |editor-last=Lovric |editor-first=Miodrag |publisher=Springer |year=2010 |isbn=978-3-642-04897-5}}</ref>
{{blockquote | The list of widely used generators that should be discarded is much longer [than the list of good generators].  Do not trust blindly the software vendors.  Check the default RNG of your favorite software and be ready to replace it if needed.  This last recommendation has been made over and over again over the past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago.}}

As an illustration, consider the widely used programming language [[Java (programming language)|Java]]. Up until 2020, Java still relied on a [[linear congruential generator]] (LCG) for its PRNG,<ref>[https://docs.oracle.com/javase/8/docs/api/java/util/Random.html Random (Java Platform SE 8)], Java Platform Standard Edition 8 Documentation.</ref><ref>[http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/Random.java Random.java] at [[OpenJDK]].</ref> which is of low quality (see further below). Java support was upgraded with [[Java version history#Java 17|Java 17]].

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]].

==Generators based on linear recurrences==
In the second half of the 20th century, the standard class of algorithms used for PRNGs comprised [[linear congruential generator]]s. The quality of LCGs was known to be inadequate, but better methods were unavailable.  Press et&nbsp;al. (2007) described the result thus: "If all scientific papers whose results are in doubt because of [LCGs and related] were to disappear from library shelves, there would be a gap on each shelf about as big as your fist."<ref>Press et&nbsp;al. (2007) §7.1</ref>

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 register]]s.

The 1997 invention of the [[Mersenne Twister]],<ref>{{cite journal|last=Matsumoto|first=Makoto|author2=Nishimura, Takuji |title=Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator|journal=ACM Transactions on Modeling and Computer Simulation|year=1998|volume=8|issue=1|pages=3–30|doi=10.1145/272991.272995|publisher=[[Association for Computing Machinery|ACM]]|s2cid=3332028 |url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf}}</ref> in particular, avoided many of the problems with earlier generators. The Mersenne Twister has a period of 2<sup>19&nbsp;937</sup>&nbsp;−&nbsp;1 iterations (≈&nbsp;4.3{{e|6001}}), 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,<ref>{{cite journal
| first=George
| last=Marsaglia
| title=Xorshift RNGs
| journal=[[Journal of Statistical Software]]
| volume=8
| issue=14
|date=July 2003
| doi=10.18637/jss.v008.i14
 | doi-access=free| s2cid=250501391
| url=http://www.jstatsoft.org/v08/i14/paper
}}</ref> again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests.<ref>{{cite web|author=S.Vigna|title=xorshift*/xorshift+ generators and the PRNG shootout|url=http://prng.di.unimi.it}}</ref><ref>Vigna S. (2016), "An experimental exploration of Marsaglia’s xorshift generators", <em>[[ACM Transactions on Mathematical Software]]</em>, 42; {{doi|10.1145/2845077}}.</ref><ref>Vigna S. (2017), "Further scramblings of Marsaglia’s xorshift generators", <em>Journal of Computational and Applied Mathematics</em>, 315; {{doi|10.1016/j.cam.2016.11.006}}.</ref>

In 2006, the [[well equidistributed long-period linear|WELL]] family of generators was developed.<ref>{{cite journal|last1=Panneton|first1=François| author2=L'Ecuyer, Pierre| author3=Matsumoto, Makoto |title= Improved long-period generators based on linear recurrences modulo 2| journal=[[ACM Transactions on Mathematical Software]] |year=2006|volume=32|issue=1|pages=1–16| doi=10.1145/1132973.1132974|s2cid=7368302 |url=http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf}}</ref> The WELL generators in some ways improves on the quality of the Mersenne Twister, which has a too-large state space and a very slow recovery from state spaces with a large number of zeros.

== Counter-based RNGs ==
{{Main|Counter-based random number generator}}
A counter-based random number generation (CBRNG, also known as a counter-based pseudo-random number generator, or CBPRNG) is a kind of PRNG that uses only an integer counter as its internal state:

<math display="block">\text { output }=f(n, \text { key })</math>

They are generally used for generating pseudorandom numbers for large parallel computations, such as over GPU or CPU clusters.<ref name="salmon-desres">{{Cite conference |last1=Salmon |first1=John |last2=Moraes |first2=Mark |last3=Dror |first3=Ron |last4=Shaw |first4=David |date=2011 |title=Parallel random numbers: as easy as 1, 2, 3 |doi=10.1145/2063384.2063405 |book-title=Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16}}</ref> They have certain advantages:

* The only “state” needed is the counter value and the key. For a given counter and key, the output is always the same. This property makes CBRNGs reproducible.
* Because each random number is computed independently of any previous outputs, they can be generated in parallel. For example, in a massively parallel application, each thread or GPU core can be assigned a range of counter values and compute random numbers without synchronization or shared state.
* Since the generator does not require stepping through every intermediate state, it can “jump” to any point in the sequence in constant time. This is particularly useful in applications like [[Monte Carlo method|Monte Carlo simulations]] where independent streams are needed.

Examples include:<ref name="salmon-desres" />

* Philox: Uses multiplication-based mixing to combine the counter and key.
* Threefry: Based on a reduced-strength version of the [[Threefish]] block cipher.

=={{Anchor|Cryptographically secure pseudorandom number generators}}Cryptographic PRNGs==
{{Main article|Cryptographically secure pseudorandom number generator}}
A PRNG suitable for [[cryptography|cryptographic]] applications is called a ''cryptographically-secure PRNG'' (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only [[negligible function|negligible]] [[advantage (cryptography)|advantage]] in distinguishing the generator's output sequence from a random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to [[polynomial time]] in the size of the seed. Though a proof of this property is beyond the current state of the art of [[computational complexity theory]], strong evidence may be provided by [[reduction (complexity)|reducing]] to the CSPRNG from a [[mathematical problem|problem]] that is assumed to be [[computational hardness assumption|hard]], such as [[integer factorization]].<ref>{{Cite book|title=Cryptanalytic Attacks on RSA|author=Song Y. Yan|date=7 December 2007 |publisher=Springer, 2007|page=73|isbn=978-0-387-48741-0}}</ref> In general, years of review may be required before an algorithm can be certified as a CSPRNG.

Some classes of CSPRNGs include the following:

* [[stream cipher]]s
* [[block cipher]]s running in [[counter mode|counter]]<ref>{{cite web|url=https://www.schneier.com/fortuna.pdf|title=Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator|author1=[[Niels Ferguson]] |author2=[[Bruce Schneier]] |author3=Tadayoshi Kohno|year=2010}}</ref> or [[output feedback]] mode
* 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 (PRNG)|Fortuna]]
* combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any detectable non-randomness
* special designs based on mathematical hardness assumptions: examples include the ''Micali–Schnorr generator'',<ref>{{cite web |url=https://www.staff.uni-mainz.de/pommeren/Cryptology/Bitstream/4_Perfect/ |title=IV.4 Perfect Random Generators |work=Cryptology |author=Klaus Pommerening |publisher=[[Johannes Gutenberg University of Mainz|uni-mainz.de]] |year=2016 |access-date=2017-11-12 }}</ref> [[Naor-Reingold Pseudorandom Function|Naor-Reingold pseudorandom function]] and the [[Blum Blum Shub]] algorithm, which provide a strong security proof (such algorithms are rather slow compared to traditional constructions, and impractical for many applications)
* generic PRNGs: while it has been shown that a (cryptographically) secure PRNG can be constructed generically from any [[one-way function]],<ref name="GoldreichLevinNotes">{{cite web | url=http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture11.pdf | title=Lecture 11: The Goldreich-Levin Theorem | work=COM S 687 Introduction to Cryptography | access-date=20 July 2016 | author=Pass, Rafael}}</ref> this generic construction is extremely slow in practice, so is mainly of theoretical interest.

It has been shown to be likely that the [[National Security Agency|NSA]] has inserted an asymmetric <!--[[kleptographic]]--> [[backdoor (computing)|backdoor]] into the [[NIST]]-certified pseudorandom number generator [[Dual_EC_DRBG]].<ref>{{cite web|url=http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html|title=The Many Flaws of Dual_EC_DRBG|author=[[Matthew D. Green|Matthew Green]]|date=18 September 2013 }}</ref>

Most PRNG algorithms produce sequences that are [[uniform distribution (discrete)|uniformly distributed]] by any of several tests. 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. In this setting, the distinguisher knows that either the known PRNG algorithm was used (but not the state with which it was initialized) or a truly random algorithm was used, and has to distinguish between the two.<ref>{{Cite book|last1=Katz|first1=Jonathan|last2=Yehuda|first2=Lindell|title=Introduction to modern cryptography|publisher=CRC press|date=2014|page=70}}</ref> 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 cipher]]s, 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 size of its period is an important factor in the cryptographic suitability of a PRNG, but not the only one.

==BSI evaluation criteria==
The German [[Federal Office for Information Security]] ({{Langx|de|Bundesamt für Sicherheit in der Informationstechnik}}, BSI) has established four criteria for quality of deterministic random number generators.<ref name=bsi_ais20>{{cite web|last=Schindler|first=Werner|title=Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators|url=https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_20_Functionality_Classes_Evaluation_Methodology_DRNG_e.pdf?__blob=publicationFile|work=Anwendungshinweise und Interpretationen (AIS)|publisher=[[Bundesamt für Sicherheit in der Informationstechnik]]|access-date=19 August 2013|pages=5–11|date=2 December 1999}}</ref> They are summarized here:

* K1 – There should be a high probability that generated sequences of random numbers are different from each other.
* K2 – A sequence of numbers is indistinguishable from "truly 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 [[Federal Office for Information Security|BSI]]<ref name=bsi_ais20 /> and [[NIST]],<ref>{{cite web|title=Security requirements for cryptographic modules |url=http://csrc.nist.gov/publications/fips/fips1401.htm |work=[[Federal Information Processing Standard|FIPS]] |publisher=[[NIST]] |access-date=19 August 2013 |page=4.11.1 Power-Up Tests |date=1994-01-11 |url-status=dead |archive-url=https://web.archive.org/web/20130527090643/http://csrc.nist.gov/publications/fips/fips1401.htm |archive-date=May 27, 2013 }}</ref> 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 an attacker (for all practical purposes) to calculate, or otherwise guess, from any given subsequence, 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 K3 or K4 standards are acceptable.

==Mathematical definition==
Given:

* <math>P</math> – a probability distribution on <math>\left(\mathbb{R},\mathfrak{B}\right)</math> (where <math>\mathfrak{B}</math> is the [[sigma-algebra]] of all [[Borel set|Borel subsets]] of the real line)
* <math>\mathfrak{F}</math> – a non-empty collection of Borel sets <math>\mathfrak{F}\subseteq\mathfrak{B}</math>, e.g. <math>\mathfrak{F}=\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}</math>. If <math>\mathfrak{F}</math> is not specified, it may be either <math>\mathfrak{B}</math> or <math>\left\{\left(-\infty,t\right] : t\in\mathbb{R}\right\}</math>, depending on context.
* <math>A\subseteq\mathbb{R}</math> – a non-empty set (not necessarily a Borel set). Often <math>A</math> is a set between <math>P</math>'s [[Support (mathematics)|support]] and its [[Interior (topology)|interior]]; for instance, if <math>P</math> is the uniform distribution on the interval <math>\left(0,1\right]</math>, <math>A</math> might be <math>\left(0,1\right]</math>. If <math>A</math> is not specified, it is assumed to be some set contained in the support of <math>P</math> and containing its interior, depending on context.

We call a function <math>f:\mathbb{N}_1\rightarrow\mathbb{R}</math> (where <math>\mathbb{N}_1=\left\{1,2,3,\dots\right\}</math> is the set of positive integers) a '''pseudo-random number generator for <math>P</math> given <math>\mathfrak{F}</math> taking values in <math>A</math>''' [[if and only if]]:

* <math>f\left(\mathbb{N}_1\right)\subseteq A</math>
* <math>\forall E\in\mathfrak{F} \quad \forall \varepsilon>0 \quad \exists N\in\mathbb{N}_1 \quad \forall n\geq N, \quad \left|\frac{\#\left\{i\in\left\{1,2,\dots, n\right\} : f(i)\in E\right\}}{n}-P(E)\right|< \varepsilon</math>

(<math>\#S</math> denotes the number of elements in the finite set <math>S</math>.)

It can be shown that if <math>f</math> is a pseudo-random number generator for the uniform distribution on <math>\left(0,1\right)</math> and if <math>F</math> is the [[Cumulative distribution function|CDF]] of some given probability distribution <math>P</math>, then <math>F^*\circ f</math> is a pseudo-random number generator for <math>P</math>, where <math>F^*:\left(0,1\right)\rightarrow\mathbb{R}</math> is the percentile of <math>P</math>, i.e. <math>F^*(x):=\inf\left\{t\in\mathbb{R} : x\leq F(t)\right\}</math>. Intuitively, an arbitrary distribution can be simulated from a simulation of the standard uniform distribution.

==Early approaches==
An early computer-based PRNG, suggested by [[John von Neumann]] in 1946, is known as the [[middle-square method]]. The algorithm is as follows: take any number, square it, remove the middle digits of the resulting number as the "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 then available, 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 hundred times faster than reading numbers in from [[punched card]]s.

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

A recent innovation is to combine the middle square with a [[Weyl sequence]]. This method produces high-quality output through a long period (see [[middle-square method]]<!-- [[middle-square method#Middle Square Weyl Sequence PRNG|Middle-Square Weyl Sequence PRNG]] -->).

==Non-uniform generators==
{{Main article|Pseudo-random number sampling}}
Numbers selected from a non-uniform probability distribution can be generated using a [[Uniform distribution (continuous)|uniform distribution]] PRNG and a function that relates the two distributions.

First, one needs the [[cumulative distribution function]] <math>F(b)</math> of the target distribution <math>f(b)</math>:

:<math>F(b)=\int_{-\infty}^b f(b') \, db'</math>

Note that <math>0=F(-\infty)\leq F(b) \leq F(\infty)=1</math>.  Using a random number ''c'' from a uniform distribution as the probability density to "pass by", we get

:<math>F(b)=c</math>

so that

:<math>b=F^{-1}(c)</math>

is a number randomly selected from distribution <math>f(b)</math>. This is based on the [[inverse transform sampling]].

For example, the inverse of cumulative [[Gaussian distribution]] <math>\operatorname{erf}^{-1}(x)</math> with an ideal uniform PRNG with range (0, 1) as input <math>x</math> 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.
* Repetitive recalculation of <math>\operatorname{erf}^{-1}(x)</math> should be reduced by means such as [[ziggurat algorithm]] for faster generation.

Similar considerations apply to generating other non-uniform distributions such as [[Rayleigh distribution|Rayleigh]] and [[Poisson distribution|Poisson]].

==See also==
{{Portal|Mathematics}}
{{cols|colwidth=26em}}
* [[List of pseudorandom number generators]]
* [[Applications of randomness]]
* [[Linear congruential generator]]
* [[Low-discrepancy sequence]]
* [[Pseudorandom binary sequence]]
* [[Pseudorandom noise]]
* [[Pseudorandomness]]
* [[Random number generation]]
* [[Random number generator attack]]
* [[Randomness]]
* [[Statistical randomness]]
{{colend}}

==References==
{{Reflist}}

==Bibliography==
* Barker E., [[John Kelsey (cryptanalyst)|Kelsey J.]], [http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf ''Recommendation for Random Number Generation Using Deterministic Random Bit Generators''], [[NIST]] SP800-90A, January 2012
* [[Richard P. Brent|Brent R.P.]], "Some long-period random number generators using shifts and xors", ''[[ANZIAM Journal]]'', 2007; 48:C188–C202
* Gentle J.E. (2003), ''Random Number Generation and Monte Carlo Methods'', Springer.
* Hörmann W., Leydold J., Derflinger G. (2004, 2011), ''Automatic Nonuniform Random Variate Generation'', Springer-Verlag.
* [[Donald Knuth|Knuth D.E.]] ''[[The Art of Computer Programming]]'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89684-2}}. Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
* Luby M., ''Pseudorandomness and Cryptographic Applications'', Princeton Univ Press, 1996. {{ISBN|9780691025469}}
* von Neumann J., "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.
* {{cite book|last=Peterson|first=Ivars|title=The Jungles of Randomness : a mathematical safari|year=1997|publisher=John Wiley & Sons|location=New York|isbn=0-471-16449-6|url-access=registration|url=https://archive.org/details/junglesofrandomn00ivar}}
* Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), ''[[Numerical Recipes]]'' ([[Cambridge University Press]]).
* [[John Viega|Viega J.]], "[http://www.acsac.org/2003/papers/79.pdf Practical Random Number Generation in Software]", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

==External links==
* [http://simul.iro.umontreal.ca/testu01/tu01.html TestU01]: A free, state-of-the-art ([[GNU General Public License|GPL]]) [[C++]] Random Number Test Suite.
* [http://www.phy.duke.edu/~rgb/General/rand_rate.php DieHarder]: A free ([[GNU General Public License|GPL]]) [[C (programming language)|C]] Random Number Test Suite.
* "[http://www.embedded.com/design/configurable-systems/4024972/Generating-random-numbers Generating random numbers]" (in [[embedded systems]]) by Eric Uner (2004)
* "[http://eprint.iacr.org/2006/086 Analysis of the Linux Random Number Generator]" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006)
* "[http://research.microsoft.com/apps/pubs/default.aspx?id=168806 Better pseudorandom generators]" by Parikshit Gopalan, Raghu Meka, [[Omer Reingold]], [[Luca Trevisan]], and [[Salil Vadhan]] ([[Microsoft Research]], 2012)
* {{YouTube|LDPMpc-ENqY|rand() Considered Harmful}} by Stephan Lavavej (Microsoft, 2013) <!-- he maintains Visual Studio C++ STL (library) as stated here https://nuwen.net/stl.html -->
* [http://wsphynx.com/simpleApp/random.html Wsphynx] a simple online random number generator. Random numbers are generated by Javascript pseudorandom number generators (PRNGs) algorithms

{{DEFAULTSORT:Pseudorandom Number Generator}}
[[Category:Pseudorandom number generators|*]]