Pseudorandomness

Pseudorandomness refers to the property of sequences produced by deterministic algorithms that imitate certain statistical aspects of true random sequences. A pseudorandom generator takes a short initial seed and an internal state and then outputs a long stream of numbers that, from the viewpoint of many statistical tests and observers, appears random. Because the process is deterministic, the entire sequence is fixed by the seed, and with sufficient knowledge of the algorithm and state, it can be predicted.

In theory, pseudorandomness is often defined relative to an observer or a class of efficient distinguishers. A sequence is considered pseudorandom if no efficient algorithm can distinguish it from a truly random sequence with non-negligible advantage. This leads to the distinction between general pseudorandom number generators and cryptographically secure pseudorandom number generators, which are designed to remain unpredictable even when part of the internal state is known.

Common applications include numerical simulations, Monte Carlo methods, randomized algorithms, and various cryptographic systems. Desirable properties for pseudorandom generators include a long period, uniform distribution of outputs, and statistical indistinguishability from random sequences for practical purposes. However, pseudorandomness does not imply true randomness, and certain sequences may fail specific tests or exhibit hidden structure if the algorithm or seed is weak or compromised.

Limitations and risks include predictability if the internal state or seed is exposed, and the need for high-quality entropy sources to seed PRNGs in some contexts. Cryptographic uses favor cryptographically secure generators that resist state compromise and partial information leakage.