Pseudorandomness

Apseudorandomsequence of numbers is one that appears to bestatistically random,despite having been produced by a completelydeterministicand repeatable process.Pseudorandom number generatorsare often used in computer programming, as traditional sources of randomness available to humans (such as rolling dice) rely on physical processes not readily available to computer programs, although developments inhardware random number generatortechnology have challenged this.

Background

The generation of random numbers has many uses, such as forrandom sampling,Monte Carlo methods,board games,orgambling.Inphysics,however, most processes, such as gravitational acceleration, are deterministic, meaning that they always produce the same outcome from the same starting point. Some notable exceptions areradioactive decayandquantum measurement,which are both modeled as being truly random processes in the underlying physics. Since these processes are not practical sources of random numbers, pseudorandom numbers are used, which ideally have the unpredictability of a truly random sequence, despite being generated by a deterministic process.

In many applications, the deterministic process is acomputer algorithmcalled apseudorandom number generator,which must first be provided with a number called arandom seed.Since the same seed will yield the same sequence every time, it is important that the seed be well chosen and kept hidden, especially insecurityapplications, where the pattern's unpredictability is a critical feature.

In some cases where it is important for the sequence to be demonstrably unpredictable, physical sources of random numbers have been used, such as radioactive decay, atmospheric electromagnetic noise harvested from a radio tuned between stations, or intermixed timings ofkeystrokes.The time investment needed to obtain these numbers leads to a compromise: using some of these physics readings as a seed for a pseudorandom number generator.

History

Before modern computing, researchers requiring random numbers would either generate them through various means (dice,cards,roulette wheels,etc.) or use existing random number tables.

The first attempt to provide researchers with a ready supply of random digits was in 1927, when the Cambridge University Press published a table of 41,600 digits developed byL.H.C. Tippett.In 1947, theRAND Corporationgenerated numbers by the electronic simulation of a roulette wheel;the results were eventually published in 1955 asA Million Random Digits with 100,000 Normal Deviates.

In computational complexity

Intheoretical computer science,adistributionispseudorandomagainst a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage. This notion of pseudorandomness is studied incomputational complexity theoryand has applications tocryptography.

Formally, letSandTbe finite sets and letF= {f:S→T} be a class of functions. AdistributionDoverSis ε-pseudorandomagainstFif for everyfinF,thestatistical distancebetween the distributions$f(X)$and$f(Y)$,where$X$is sampled fromDand$Y$is sampled from theuniform distributiononS,is at most ε.

In typical applications, the classFdescribes a model of computation with bounded resources and one is interested in designing distributionsDwith certain properties that are pseudorandom againstF.The distributionDis often specified as the output of apseudorandom generator.

See also

• Cryptographically secure pseudorandom number generator– Type of functions designed for being unsolvable by root-finding algorithms
• List of random number generators
• Pseudorandom binary sequence– Seemingly random, difficult to predict bit stream created by a deterministic algorithm
• Pseudorandom ensemble
• Pseudorandom number generator– Algorithm that generates an approximation of a random number sequence
• Low-discrepancy sequence– Type of mathematical sequence
• Random number generation– Producing a sequence that cannot be predicted better than by random chance
• Pseudorandom noise– Pseudo-random signal with characteristics similar to noise

Further reading

• Donald E. Knuth (1997)The Art of Computer Programming,Volume 2: Seminumerical Algorithms (3rd edition).Addison-Wesley Professional,ISBN0-201-89684-2
• Goldreich, Oded (2008).Computational Complexity: A Conceptual Perspective.Cambridge University Press.ISBN978-0-521-88473-0.See especially Chapter 8: Pseudorandom generators, pp. 284–348, and Appendix C.2: Pseudorandomness, pp. 490–493.
• Vadhan, S. P. (2012). "Pseudorandomness".Foundations and Trends in Theoretical Computer Science.7(1–3): 1–336.doi:10.1561/0400000010.

External links

• HotBits: Genuine random numbers, generated by radioactive decay
• Using and Creating Cryptographic-Quality Random Numbers
• In RFC 4086, the use of pseudorandom number sequences in cryptography is discussed at length.