# Pseudorandomness

__: Appearing random but actually being generated by a deterministic, causal process__

**Short description**A **pseudorandom** sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.^{[1]}

## Background

The generation of random numbers has many uses, such as for random sampling, Monte Carlo methods, board games, or gambling. In physics, 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 are radioactive decay and quantum measurement, which are both modeled as being truly random processes in the underlying physics. Since these processes are not practical sources of random numbers, people use pseudorandom numbers, which ideally have the unpredictability of a truly random sequence, despite being generated by a deterministic process.^{[2]}

In many applications, the deterministic process is a computer algorithm called a pseudorandom number generator, which must first be provided with a number called a random 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 in security applications, where the pattern's unpredictability is a critical feature.^{[3]}

In some cases where it is important for the sequence to be demonstrably unpredictable, people have used physical sources of random numbers, such as radioactive decay, atmospheric electromagnetic noise harvested from a radio tuned between stations, or intermixed timings of people's keystrokes.^{[1]}^{[4]} 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,^{[5]} 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 by L.H.C. Tippett. In 1947, the RAND Corporation generated numbers by the electronic simulation of a roulette wheel;^{[5]} the results were eventually published in 1955 as *A Million Random Digits with 100,000 Normal Deviates*.

## In computational complexity

In theoretical computer science, a distribution is **pseudorandom** against a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage.^{[6]}
This notion of pseudorandomness is studied in computational complexity theory and has applications to cryptography.

Formally, let *S* and *T* be finite sets and let **F** = {*f*: *S* → *T*} be a class of functions. A distribution **D** over *S* is ε-**pseudorandom** against **F** if for every *f* in **F**, the statistical distance between the distributions and [math]\displaystyle{ f(X) }[/math], where and [math]\displaystyle{ X }[/math] is sampled from **D**, and [math]\displaystyle{ f(Y) }[/math], where and [math]\displaystyle{ Y }[/math] is sampled from the uniform distribution on *S*, is at most ε.

In typical applications, the class **F** describes a model of computation with bounded resources and one is interested in designing distributions **D** with certain properties that are pseudorandom against **F**. The distribution **D** is often specified as the output of a pseudorandom generator.^{[7]}

## See also

- Cryptographically secure pseudorandom number generator
- List of random number generators
- Pseudorandom binary sequence
- Pseudorandom ensemble
- Pseudorandom number generator
- Quasi-random sequence
- Random number generation
- Pseudorandom noise

## References

- ↑
^{1.0}^{1.1}George Johnson (June 12, 2001). "Connoisseurs of Chaos Offer A Valuable Product: Randomness".. https://www.nytimes.com/2001/06/12/science/connoisseurs-of-chaos-offer-a-valuable-product-randomness.html.*The New York Times* - ↑ S. P. Vadhan (2012).
*Pseudorandomness*. "pseudorandomness, the theory of efficiently generating objects that “look random” despite being constructed using little or no randomness" - ↑ Mark Ward (August 9, 2015). "Web's random numbers are too weak, researchers warn".
*BBC*. https://www.bbc.com/news/technology-33839925. - ↑ Jonathan Knudson (January 1998). "Javatalk: Horseshoes, hand grenades and random numbers".
*Sun Server*: 16–17. - ↑
^{5.0}^{5.1}"A Million Random Digits". RAND Corporation. http://www.rand.org/pubs/monograph_reports/MR1418/index2.html. - ↑ Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
- ↑ "Pseudorandomness". https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug12.pdf.

## Further reading

- Donald E. Knuth (1997)
*The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)*. Addison-Wesley Professional, ISBN 0-201-89684-2 - Oded Goldreich. (2008)
*Computational Complexity: a conceptual perspective*. Cambridge University Press. ISBN 978-0-521-88473-0.**(Limited preview at Google Books)** - 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 1750, the use of pseudorandom number sequences in cryptography is discussed at length.

Original source: https://en.wikipedia.org/wiki/Pseudorandomness.
Read more |