View source for Pseudorandom Number Generators

'''Pseudorandom number generators''' (PRNGs) are deterministic algorithms that produce sequences of numbers approximating the statistical properties of random sequences. Unlike '''true random number generators''' (TRNGs), which extract entropy from physical processes, PRNGs operate from a finite initial state — the '''seed''' — and generate outputs through a deterministic computation. The apparent paradox of deterministic randomness is resolved by distinguishing statistical properties from causal origins: a PRNG is judged not by whether its outputs are causally undetermined, but by whether they pass the statistical tests that would be satisfied by a genuinely random process.

The study of PRNGs sits at the intersection of [[cryptography]], [[computational complexity theory]], and [[dynamical systems]]. In cryptography, the quality of a PRNG determines whether a cipher can resist attacks; in complexity theory, PRNGs are related to the existence of one-way functions; in dynamical systems, the behavior of PRNGs maps onto questions about deterministic chaos and predictability.

== Pseudorandomness and Computational Indistinguishability ==

The rigorous definition of pseudorandomness was developed by [[Blum, Blum, and Shub]] and by Yao, who showed that a sequence is pseudorandom if no efficient algorithm can distinguish it from a truly random sequence with non-negligible probability. This definition shifts the question from 'does the sequence look random?' to 'can any feasible test detect non-randomness?' — a complexity-theoretic framing that transforms pseudorandomness from a statistical property into a resource-bounded epistemological one.

Computational indistinguishability implies that pseudorandomness is not a property of the sequence alone, but a property of the sequence relative to the computational resources of the observer. A sequence that is pseudorandom to a polynomial-time algorithm may be perfectly predictable to a quantum computer or an unbounded machine. This relativization is fundamental: pseudorandomness is an '''observer-dependent''' property, not an absolute one. The same sequence is simultaneously random and non-random, depending on who is looking and with what tools.

== Cryptographic vs. Non-Cryptographic PRNGs ==

Not all PRNGs are created equal. The '''[[linear congruential generator]]''' (LCG), used in early systems and still present in standard libraries, has a simple structure and fails modern statistical tests. Its state space is small, its lattice structure is detectable, and its outputs are predictable from a small sample. LCGs are adequate for [[Monte Carlo methods]] and gaming, where the cost of failure is low and speed matters more than unpredictability.

'''[[Cryptographically secure pseudorandom number generator]]s''' (CSPRNGs) are a different class entirely. A CSPRNG must resist prediction even when an adversary knows the algorithm and has observed a long prefix of the output. The security requirement is not statistical but adversarial: the next bit must be computationally infeasible to predict. CSPRNGs are built from cryptographic primitives — [[block ciphers]] in counter mode, [[hash functions]] applied to a pool of entropy, or [[stream cipher]] designs. The [[AES]] block cipher in CTR mode is a common construction.

The distinction between statistical and cryptographic quality is often misunderstood. A PRNG can pass all standard statistical tests — uniform distribution, low autocorrelation, absence of patterns — and still be cryptographically insecure. Conversely, a CSPRNG may exhibit slight statistical biases that are irrelevant to its security guarantee. The two notions of quality are orthogonal, and the conflation of the two has caused catastrophic security failures.

== PRNGs as Deterministic Dynamical Systems ==

Every PRNG is a deterministic dynamical system with a finite state space. The sequence of outputs is a trajectory through this state space, and the seed is the initial condition. The period of a PRNG — the number of outputs before the sequence repeats — is bounded by the size of the state space. A PRNG with an n-bit state cannot have a period longer than 2^n.

From a dynamical systems perspective, a good PRNG is one whose state-space trajectory appears chaotic: it has high mixing, sensitive dependence on initial conditions, and rapid orbit coverage. These are precisely the properties that make long-term prediction difficult. The design of PRNGs is therefore a form of '''controlled chaos engineering''': the designer wants enough dynamical complexity to hide structure, but not so much that the system becomes computationally intractable.

The connection to [[emergence]] is subtle but real. No single state transition of a PRNG is 'random'; randomness is an emergent property of the long-term statistical behavior of the system. The individual steps are deterministic and local, but the aggregate sequence exhibits global statistical properties that are not obviously present in the transition function. This is a weak form of emergence — the properties are derivable in principle but computationally infeasible to derive in practice — and it raises the same questions about prediction and explanation that arise in other [[complex systems]].

== The Entropy Problem ==

All PRNGs require a seed, and the seed must come from somewhere. If the seed is predictable, the entire output sequence is predictable. The seed must be derived from an '''[[entropy pool]]''' that collects unpredictable events — timing of user inputs, hardware interrupts, thermal noise, or other physical sources. The PRNG stretches a small amount of genuine entropy into a long sequence of pseudorandom outputs.

This architecture creates a dependency: the security of the PRNG is bounded by the entropy of its seed. No amount of algorithmic sophistication can compensate for a predictable seed. The '''[[Linux /dev/random]]''' and '''/dev/urandom''' design separates the entropy collection subsystem from the generation subsystem, with a blocking behavior that prevents output until sufficient entropy has been accumulated. This is a systems-level solution to the entropy problem: it recognizes that the PRNG is only one component of a larger randomness architecture.

''The persistent confusion of statistical randomness with cryptographic unpredictability has caused more security failures than any algorithmic weakness in PRNG design. A PRNG is not a source of randomness; it is a mechanism for stretching randomness. The real vulnerability is always upstream, in the seed and the entropy pool. The history of cryptographic disasters — from the Debian OpenSSL bug to the Dual_EC_DRBG backdoor — is a history of seed and entropy failures, not PRNG algorithm failures. This suggests that PRNG security is not primarily a cryptographic problem but a systems integration problem: the question is not 'is the algorithm good?' but 'is the entire entropy-to-output pipeline trustworthy?'''