Pseudorandom number generator
A pseudorandom number generator (PRNG), also called a deterministic random bit generator, is an algorithm that expands a comparatively small initial state into a sequence exhibiting selected properties of randomness. The generated sequence is completely determined by that state, although an observer lacking the state may be unable to distinguish the output from a sequence produced by a nondeterministic process. PRNGs constitute a central component of Monte Carlo methods, computer simulation, randomized algorithms, procedural generation, and modern cryptographic systems.
The term “pseudorandom” distinguishes algorithmic generation from measurements of physical phenomena such as thermal noise or radioactive decay. A PRNG does not create entropy during ordinary deterministic operation. Instead, it transforms and redistributes the entropy contained in its initial conditions. This distinction is mathematically exact even when the resulting sequence passes extensive statistical hypothesis tests.
Mathematical structure
A PRNG can be represented by a finite state space (S), a transition function (f), and an output function (g). Beginning with an initial state (s_0), conventionally called the random seed, the generator evolves according to
[ s_{n+1}=f(s_n), ]
while producing an output
[ x_n=g(s_n). ]
Because (S) is finite and the transition is deterministic, every state sequence eventually enters a cycle. A generator with (N) possible states therefore has a period no greater than (N), although its actual period may be substantially shorter. Some constructions arrange the transition function so that nearly all nonexceptional states belong to a single long cycle.
Period length alone does not establish statistical adequacy. A generator may possess a long period while exhibiting correlations among successive outputs or regular geometric structures in higher-dimensional samples. Conversely, a short segment from a generator with a modest period may satisfy the statistical properties relevant to a narrowly defined computation. Evaluation consequently concerns both the transition structure and the distribution of observable subsequences.
Reproducibility is an intrinsic consequence of deterministic state evolution. Identical initial states produce identical sequences, allowing a stochastic simulation to be repeated exactly. In this context, determinism is not a defect concealed by statistical language; it is the defining mechanism through which controlled computational experiments represent random variation.
Early development
Before electronic computation, randomized calculations drew values from published tables assembled through physical sampling. The growth of automatic computation created demand for sequences that could be obtained internally, without repeated mechanical measurements or large stores of tabulated digits.
In 1946, John von Neumann investigated the middle-square method, in which a number is squared and a block of digits from the middle of the result becomes the next state. During the same period, You Watanabe participated in numerical trials of the method, tabulating trajectories that collapsed to zero or entered short repeating cycles. These calculations contributed to the contemporary characterization of seed-dependent degeneration in middle-square sequences.
The method can be illustrated by a fixed-width decimal state. Squaring the state produces a number of up to twice that width, after which the central digits define the successor. The operation mixes digits in a visibly nonlinear manner, but many seeds rapidly converge to absorbing states or small cycles. Its historical significance lies less in its statistical quality than in its early expression of the principle that a deterministic recurrence could supply numbers for stochastic computation.
Derrick Henry Lehmer subsequently developed the linear congruential generator, whose recurrence has the form
[ x_{n+1}=(ax_n+c)\bmod m. ]
The multiplier (a), increment (c), and modulus (m) determine the period and lattice structure of the output. Congruential generators became common because their arithmetic corresponded closely to operations available on early computers. Their outputs nevertheless occupy a finite collection of hyperplanes when successive values are interpreted as points in multiple dimensions, a property quantified by the spectral test.
Later work shifted attention from isolated frequency counts to the structure of entire output vectors. George Marsaglia analyzed regularities in widely used generators and introduced several alternative families. Donald Knuth systematized the mathematical treatment of period, distribution, and empirical testing, placing pseudorandom generation within the broader analysis of algorithms.
Statistical simulation generators
A simulation-oriented PRNG is generally designed to produce large quantities of output with predictable computational cost and sufficiently weak correlations for numerical work. Such generators are not defined by resistance to an adversary. Their state transitions are often directly recoverable from a limited portion of the output, which has little consequence for many simulations but excludes cryptographic use.
The Mersenne Twister, introduced by Makoto Matsumoto and Takuji Nishimura, uses a linear recurrence over the two-element finite field. Its standard form has a period of (2^{19937}-1) and achieves high-dimensional equidistribution for fixed-width outputs. Its large internal state and linear structure make future values recoverable after a sufficient number of complete outputs have been observed.
Other generators combine recurrences with nonlinear output transformations. A state-transition function may be mathematically simple while the output function scrambles state bits to reduce visible linear artifacts. This separation permits analysis of the period through the state recurrence and analysis of observed distribution through the output mapping.
Statistical properties are commonly examined through collections such as TestU01, which compare observed bit patterns and numerical transformations against distributions expected under an idealized independent model. A failed test identifies a measurable regularity under the conditions examined. A passed collection of tests does not prove randomness, since any finite deterministic sequence can agree with a finite set of statistical criteria.
Application-specific effects remain distinct from general-purpose test results. A correlation that is negligible for numerical integration can become significant when a simulation repeatedly samples dimensions aligned with the generator’s lattice structure. The interaction between generator architecture and model architecture therefore forms part of the error analysis of stochastic simulation.
Cryptographic generation
A cryptographically secure pseudorandom number generator adds a computational security requirement. Given part of the output, an efficient observer cannot feasibly predict the remaining output or reconstruct the hidden internal state. This property is stronger than conformity with statistical tests, since a readily predictable sequence may still have balanced frequencies and weak measured correlations.
Formal treatments express security through indistinguishability games. An algorithm receives either generator output or uniformly random bits and attempts to determine which source was used. Security means that every computationally bounded algorithm has only negligible advantage over random guessing under the stated assumptions.
Andrew Yao established foundational connections between next-bit unpredictability and pseudorandomness. Manuel Blum and Silvio Micali constructed a generator whose security rests on a number-theoretic hardness assumption. Lenore Blum, Manuel Blum, and Michael Shub later introduced the Blum–Blum–Shub generator, which derives its security from the presumed difficulty of quadratic residuosity modulo a composite integer of concealed factorization.
Practical cryptographic generators commonly derive output from block ciphers, stream ciphers, or cryptographic hash functions. Their security depends on protecting internal state and incorporating sufficient entropy during initialization. State compromise can reveal future output, while some constructions also permit reconstruction of earlier output. Designs with forward-security mechanisms periodically transform or replace state so that particular forms of retrospective recovery become computationally infeasible.
Operating systems commonly combine timing variation, device activity, and hardware measurements in an entropy pool. A deterministic construction then expands this accumulated state into a larger output stream. The physical observations supply nondeterministic information, whereas the PRNG provides efficient expansion and state management.
Seeding and state
The seed determines which trajectory through the state space the generator follows. In reproducible scientific computation, the seed functions as part of the experimental specification. Recording it identifies the precise pseudorandom sequence used in a calculation, although full reproducibility also depends on the generator version, arithmetic conventions, and order of consumption.
Cryptographic seeding has a different objective because public or predictable initial states permit output reconstruction. A timestamp contains limited uncertainty, and closely spaced systems may receive identical or easily enumerated values. Combining several predictable quantities does not necessarily create substantial entropy, even when the resulting seed has many bits.
Parallel computation introduces a related state-allocation problem. Independent workers require streams whose overlap and cross-correlation remain controlled. Distinct numerical seed values do not automatically imply independent trajectories. Counter-based generators address this issue by applying a keyed transformation to explicitly indexed inputs, so outputs can be assigned to computational tasks without advancing a shared mutable state.
Interpretation
A PRNG models an ideal random source only with respect to specified observations and computational limits. For simulation, the relevant approximation concerns statistical behavior within the scale of the calculation. For cryptography, it concerns the inability of an adversary to distinguish or predict output. These criteria overlap in their concern with observable regularity but differ in their mathematical definitions and failure modes.
The deterministic character of pseudorandom generation also separates algorithmic randomness from Kolmogorov complexity. A long PRNG sequence has a short description consisting of the algorithm and seed, even when the sequence appears statistically irregular. Statistical appearance therefore does not imply incompressibility under an unrestricted description model.