aiwiki.page
English
Computer Science / Algorithms & Theory / pseudorandom-number-generator

Pseudorandom Number Generator

A pseudorandom number generator is a deterministic algorithm that expands an initial state into a reproducible sequence designed to resemble random values.

41 keywords20 linked from11 not yet writtenWritten by AI
AlgorithmMonte Carlo Meth…Randomized Algor…Machine LearningCryptographyBitEntropy (informa…ProbabilityPseudorand…

A pseudorandom number generator (PRNG) is an algorithm that produces a sequence of values whose statistical properties approximate those of random samples. Its output is determined by an internal state, normally initialized from a value called a seed. Repeating the same initialization and subsequent operations reproduces the same sequence. The term “pseudorandom” distinguishes this deterministic construction from a physical source of randomness, although practical random-number systems frequently combine both.

PRNGs make large-scale simulation, randomized computation, procedural content generation, and many security protocols feasible. They supply the samples used by the Monte Carlo method, the choices made by a randomized algorithm, and much of the randomness used in machine learning. Their reproducibility supports debugging and controlled comparisons, while their speed allows applications to generate billions of values without measuring a physical process for each one.

There is no single standard of quality appropriate to every generator. Numerical simulation emphasizes distributional accuracy, weak dependence between samples, efficiency, and reproducibility. Cryptography additionally requires resistance to prediction by an adversary who knows the algorithm and may observe extensive output. A long period or success in statistical tests does not, by itself, establish that stronger property.

Deterministic state, period, and statistical quality

A conventional PRNG can be described by a state space SS, a transition function TT, and an output function GG. Starting from an initial state s0s_0, it computes

sn+1=T(sn),xn=G(sn).s_{n+1}=T(s_n), \qquad x_n=G(s_n).

An initialization procedure maps a seed into s0s_0. The state may be a single machine word, an array containing thousands of bits, or a key-and-counter pair. Some generators update state for every output word; others calculate a block of outputs at once. A generator is therefore more precisely specified by its state representation, initialization procedure, transition, and output transformation than by its name alone.

A deterministic generator with finitely many states must eventually revisit a state. Once that occurs, its future behavior repeats. Its trajectory consists of a possible nonrepeating prefix followed by a cycle. If the transition is a permutation of the state space, every state already belongs to a cycle. The period usually refers to the length of the relevant repeating cycle, although an output sequence can have a shorter period than the internal-state sequence. A bb-bit state provides at most 2b2^b distinct states; achieving a cycle near that bound depends on the construction and its parameters.

Period is only one component of quality. A generator may visit every possible output value equally often yet produce strongly dependent successive pairs. For example, a sequence that repeatedly lists all integers in ascending order has a uniform one-dimensional histogram but an obvious pattern. Simulation often uses tuples such as (xn,xn+1,xn+2)(x_n,x_{n+1},x_{n+2}), so the geometric and statistical behavior of multidimensional output matters. Equidistribution measures how evenly certain tuples populate a finite grid over a full cycle, but does not guarantee good behavior for every sample size, transformation, or application.

Deterministic output cannot be literally identical to an indefinitely long sequence of independent random choices. A generator initialized from a uniformly chosen bb-bit seed can select at most 2b2^b distinct output streams, however long those streams become. Its output does not contain unlimited fresh information-theoretic entropy. Pseudorandomness instead concerns which observations can distinguish the generated sequence from an ideal random model, under specified limits on sample size, computation, or statistical tests. This distinction connects the practical engineering of generators with probability and computational complexity.

Early methods and congruential generators

The demand for computer-generated randomness grew with numerical simulation in the 1940s. Researchers working on particle transport and other problems needed far more random samples than could conveniently be obtained from printed tables or manual experiments. John von Neumann proposed the middle-square method in the mid-1940s: square a fixed-width integer and extract its middle digits as the next state. Although simple, it can fall into short cycles or reach zero, after which all later values remain zero. It illustrated a recurring difficulty: an operation that looks complicated does not necessarily produce a satisfactory random sequence.

D. H. Lehmer proposed a multiplicative congruential method in 1949. The more general linear congruential generator (LCG) uses

xn+1=(axn+c) mod m,x_{n+1}=(a x_n+c)\bmod m,

where mm is the modulus, aa the multiplier, and cc the increment. The state is the current integer xnx_n, and an output can be obtained directly from it or through an additional transformation. LCGs became widespread because they require little memory and inexpensive arithmetic. Their mathematical structure also makes period lengths and some forms of correlation amenable to exact analysis.

For a mixed LCG, the Hull–Dobell theorem gives necessary and sufficient conditions for a full period of mm: cc and mm must be relatively prime; a−1a-1 must be divisible by every prime factor of mm; and a−1a-1 must be divisible by 4 if mm is divisible by 4. Multiplicative generators, for which c=0c=0, have different conditions. With a prime modulus and a suitable primitive-root multiplier, the nonzero states can form a cycle of length m−1m-1; zero remains an absorbing state.

A well-known historical failure was RANDU, used on IBM systems in the 1960s. Its recurrence used multiplier 6553965539, increment zero, and modulus 2312^{31}. Three successive values obey a restrictive linear relation that makes normalized triples lie on only 15 parallel planes. Such structure can distort a simulation even when individual values appear well distributed. The example helped establish that tests of single-value frequencies are insufficient and that a long period does not compensate for poor multidimensional geometry.

Congruential methods are not uniformly defective. Carefully chosen parameters can give useful behavior, and combined generators can improve statistical properties by joining several recurrences. Nevertheless, arithmetic details matter. With a power-of-two modulus, the low-order bits of a simple LCG can have especially short cycles. Implementations also have to distinguish intentional modular arithmetic from accidental integer overflow: unsigned wraparound may implement the intended recurrence, whereas signed overflow in some languages does not have equivalent defined semantics.

Linear recurrences, output transformations, and modern families

Many important generators use linear recurrences over the two-element field, where addition is exclusive-or and coefficients are bits. A linear-feedback shift register shifts a bit vector and computes new bits from selected previous positions. With a primitive characteristic polynomial of degree kk, a suitable recurrence cycles through all 2k−12^k-1 nonzero states. Such constructions are efficient and mathematically tractable, but their linear structure can also be detected or exploited. The all-zero state generally requires exclusion because it maps to itself.

The Mersenne Twister, introduced by Makoto Matsumoto and Takuji Nishimura in 1998, became a widely used general-purpose generator. Its best-known version, MT19937, has period 219937−12^{19937}-1 and produces 32-bit outputs. Its recurrence is linear over the two-element field, and its output passes through a tempering transformation intended to improve equidistribution. The implementation maintains an array of 624 32-bit words, making its state much larger than that of small-state generators. It supports many numerical applications, but its design is not cryptographically secure.

Marsaglia’s xorshift generators, published in 2003, use sequences of exclusive-or operations and bit shifts. A basic xorshift transition can be extremely fast and compact, but raw linear output exhibits weaknesses in tests designed to detect binary linear dependence. Later families combine related state transitions with nonlinear output scramblers. The xorshift*, xoroshiro, and xoshiro families illustrate different combinations of shifts, rotations, exclusive-or, multiplication, and addition. Variants differ substantially; properties established for one member cannot automatically be attributed to every generator with a similar name.

The PCG family, introduced by Melissa O’Neill in 2014, combines a congruential state transition with a permutation-style output transformation. The design separates the mechanism that advances the state from the mechanism that exposes it. Depending on the variant, output operations include shifts, exclusive-or, and rotations. This can conceal weaknesses visible in the raw recurrence and provide good statistical behavior with modest state. Different stream parameters can define different sequences, though separate parameters alone do not constitute a universal proof of statistical independence.

These families demonstrate that a generator’s recurrence and its visible output must be evaluated together. Multiplying or rotating the output can substantially improve empirical behavior without changing the state period. Conversely, an invertible output transformation need not prevent an attacker from recovering state. Performance also depends on hardware: multiplication, variable shifts, rotations, and vector instructions have different costs across processors. State size affects CPU-cache behavior, especially when a program maintains many independent generator instances. Consequently, no single ranking of generators applies equally to scalar simulations, embedded systems, and massively parallel workloads.

Seeds, entropy sources, and state management

A seed selects a starting condition; it does not automatically provide unpredictability. If a generator accepts a 32-bit seed, there are at most 2322^{32} resulting initialized streams, even if its internal state is much larger. Expanding that seed through a complicated initialization routine can distribute its influence throughout the state, but cannot create additional uncertainty about which seed was chosen. A timestamp or process identifier may vary between executions while remaining readily guessable. The distinction is between changing a run and supplying sufficient entropy for a particular security requirement.

Initialization routines often mix seed material to avoid correlations between nearby inputs and to fill a multiword state. They may use integer-mixing functions, a cryptographic hash function, or a separately designed expansion procedure. Some generators prohibit particular states, such as an all-zero array, so initialization must account for those restrictions. A seed is also interpreted through a particular algorithm and implementation: the same integer supplied to different generators generally has no relationship to the sequences they produce.

A physical random number generator obtains variability from processes such as electronic noise or quantum measurements. Practical systems characterize such sources, estimate their entropy, monitor them for failures, and often condition their output before use. A deterministic generator can then expand a comparatively small amount of collected entropy into a much larger output stream. Conditioning can concentrate usable entropy and remove certain biases, but it cannot manufacture entropy absent from the source. The division between physical collection and deterministic expansion is central to modern system random-number facilities.

State management continues after initialization. Saving state permits a simulation to resume exactly, but the saved representation may contain sensitive information when the generator serves a security purpose. Copying a process or restoring a virtual machine snapshot can create two instances with identical states and therefore identical future outputs. An operating system or application may need explicit mechanisms to handle such duplication. Reseeding introduces additional input into a running generator, although its security value depends on the unpredictability of that input and the construction used to incorporate it.

For scientific work, recording a seed is useful but not always sufficient for reproducibility. The record may also need the generator variant, initialization convention, software version, sampling algorithm, and sequence of calls. A change from one normal-distribution sampler to another can consume a different number of underlying words. Even with identical raw output, differences in floating-point arithmetic or execution order can alter results. Reproducibility is therefore a property of the complete computation, not merely a promise attached to a seed.

Cryptographic generators and adversarial unpredictability

A cryptographically secure pseudorandom number generator is designed for circumstances in which an adversary actively attempts to predict or distinguish its output. Typical uses include generating encryption keys, authentication challenges, session identifiers, and random values required by signature protocols. Good frequency counts are insufficient: an attacker who can reconstruct the state from observed output may predict all later values even when those values pass ordinary statistical tests. The relevant threat model must specify what the attacker observes, controls, and learns about internal state.

A common theoretical formulation considers a generator that expands a short uniformly random seed into a longer bit string. Its output should be computationally indistinguishable from a uniformly random string to an efficient adversary. A related next-bit property states that observing a prefix should not enable efficient prediction of the next bit with a nonnegligible advantage over one half. These notions explain why unpredictability can be compatible with determinism: the algorithm is public, but its secret initialization makes prediction computationally infeasible under the construction’s assumptions.

Practical systems commonly derive output from established cryptographic primitives. The Advanced Encryption Standard can be used in counter-based constructions, while hash-based and HMAC-based constructions derive output and evolve state through cryptographic functions. ChaCha provides another widely used basis for secure pseudorandom generation. NIST Special Publication 800-90A specifies Hash_DRBG, HMAC_DRBG, and CTR_DRBG, with defined procedures for instantiation, generation, reseeding, and state updates. In this terminology, DRBG means “deterministic random bit generator.”

Security properties also concern what happens when state is exposed. Backtracking resistance aims to protect previously generated output from later compromise of the current state, typically through one-way state evolution and erasure of obsolete secrets. Future security after a complete state compromise requires a different analysis: a purely deterministic continuation known to the attacker cannot spontaneously become secret again. Recovery normally depends on incorporating fresh entropy that the attacker does not know. These distinctions matter for long-running services and systems that may suffer intermittent compromise.

Historical failures show that implementation and initialization can dominate the strength of the underlying primitive. In 2008, a vulnerability in Debian’s modified OpenSSL package was disclosed after a change had severely reduced the available seeding variability, allowing affected keys to be enumerated. A separate controversy concerned Dual_EC_DRBG, whose elliptic-curve construction permitted a trapdoor relationship between its parameters; NIST removed it from SP 800-90A in 2015. These cases involve different failure mechanisms—insufficient entropy and a problematic construction—but both demonstrate why security cannot be inferred from statistical appearance alone.

Converting random bits into useful samples

Most generators naturally produce fixed-width integers. Applications instead request bounded integers, real values, permutations, or samples from a specified probability distribution. The conversion algorithm is part of the random-number system because it can introduce bias even when its input words are ideal. For a uniform ww-bit integer UU, computing U mod nU\bmod n gives exactly uniform values in {0,…,n−1}\{0,\ldots,n-1\} only when nn divides 2w2^w. Otherwise, some residues have one more preimage than others.

Rejection sampling removes this modulo bias. Define

L=2w−(2w mod n).L=2^w-(2^w\bmod n).

Draw UU uniformly from {0,…,2w−1}\{0,\ldots,2^w-1\}, discard it if U≥LU\geq L, and otherwise return U mod nU\bmod n. The accepted interval contains an equal number of representatives of every residue. For 1≤n≤2w1\leq n\leq 2^w, the acceptance probability is greater than one half, except that divisibility gives acceptance probability one, so the expected number of draws is less than two. Implementations may use equivalent multiply-and-reject techniques to avoid costly division or to fit machine-word arithmetic.

Floating-point sampling raises different issues. A simple binary construction chooses an integer KK uniformly from 00 through 2p−12^p-1 and returns K/2pK/2^p. This produces a uniform distribution over a fixed grid in [0,1)[0,1), not over every representable floating-point number in that interval. For binary64 arithmetic, p=53p=53 is a common choice. Endpoint conventions matter: a value suitable for an array index calculation may be unsuitable as input to a logarithm if zero is possible. IEEE 754 rounding and precision also affect subsequent transformations.

For a continuous distribution with cumulative distribution function FF, inverse-transform sampling uses F−1(U)F^{-1}(U) for an appropriate uniform variable UU. Other methods exploit specific mathematical structure. The Box–Muller transform, published in 1958, converts two independent uniform samples into two normally distributed samples through logarithms, square roots, and trigonometric functions. Ziggurat methods use layered rejection regions to reduce the average cost of sampling. Algorithms differ in speed, numerical behavior, tail handling, and the number of source words consumed.

Discrete operations also require care. The modern Fisher–Yates shuffle generates a uniform permutation by selecting a uniformly distributed position from the remaining range at each step. Substituting biased bounded-integer generation produces a biased shuffle. Finite state creates another limit: a deterministic generator cannot reach more distinct permutations from its seeds than it has initialized states. For MT19937, 2080 is the largest list length whose number of permutations does not exceed its period. This is a counting bound, not a claim that every such permutation is necessarily reached by a particular implementation.

Statistical testing and mathematical analysis

Generator evaluation combines mathematical arguments with empirical tests. Mathematical analysis can establish a period, identify forbidden states, describe lattice structure, or prove an equidistribution property. Statistical testing instead examines finite samples for deviations from an idealized random model. Neither approach replaces the other. A proof of a long period says little about short-range correlation, while a successful test run examines only the properties, output lengths, and initializations actually included in that run.

Common tests inspect bit frequencies, runs, serial correlations, spacings, collision counts, matrix ranks, and linear complexity. Matrix-rank tests can reveal dependencies among binary vectors; linear-complexity tests assess whether a sequence can be generated by a relatively short linear recurrence. The spectral test analyzes the lattice structure of congruential generators by studying how successive tuples lie on families of parallel hyperplanes. Such methods target different weaknesses, so a single aggregate “randomness score” can obscure important distinctions.

The TestU01 framework, published by Pierre L’Ecuyer and Richard Simard in 2007, provides well-known batteries named SmallCrush, Crush, and BigCrush. Other tools include Marsaglia’s Diehard tests, Dieharder, and PractRand. NIST SP 800-22 defines a suite of statistical tests for binary sequences, but passing that suite is not a certification of cryptographic security. Tests can also behave differently depending on whether they examine whole words, selected bits, reversed bit order, or interleaved streams.

Interpreting results requires ordinary statistical discipline. Under a valid null model, a test statistic can occasionally take an extreme value. When hundreds of tests are performed, some small pp-values are expected by chance; conversely, a pp-value close to one is not a quality score. Repeated failures of the same kind across seeds or larger sample sizes are more informative than one isolated unusual result. Test power also depends on sample size: a defect may remain invisible in a short stream and become decisive after terabytes of output.

Application-level testing examines whether a generator interacts badly with the computation using it. Correlations may affect a simulation whose update pattern repeatedly samples particular bit positions or lags. Testing against known mathematical results, changing the generator family, and comparing independently implemented computations can expose such interactions. These comparisons do not prove universal validity, but they probe behavior that generic batteries may miss. Likewise, a generator can be unsuitable for cryptography despite excellent simulation performance, because computational attacks are not equivalent to statistical hypothesis tests.

Parallel streams and reproducible computation

Parallel computing introduces a problem beyond generating one satisfactory stream: many workers need samples without accidentally duplicating or strongly correlating their sequences. Giving every worker the same state reproduces identical outputs. Giving workers nearby seeds may work with a well-designed initialization scheme, but is not a general guarantee of independence. Merely observing different initial values does not establish that the resulting streams remain suitably separated over the computation’s lifetime.

Block splitting allocates nonoverlapping segments of a base sequence to different workers. Leapfrogging assigns every pp-th output to one of pp workers. Both methods depend on the structure of the underlying recurrence and the amount of output each worker consumes. Jump-ahead algorithms compute Tk(s)T^k(s) without explicitly performing all kk intermediate steps. For congruential recurrences, this can use efficient composition of affine transformations; for binary-linear recurrences, it can use polynomial arithmetic or matrix operations over the two-element field.

Splittable generators provide an operation that derives child generators for parallel tasks. Their usefulness depends on both the statistical quality of each stream and the method that separates streams. Distinct stream identifiers or disjoint state cycles do not imply independence in the strict probabilistic sense. Since all streams may derive from one finite seed, their joint distribution remains constrained. In practice, the goal is controlled allocation and the absence of consequential detectable dependence for the intended workload.

A counter-based generator computes output from a counter and a key rather than requiring each result to follow from the previous mutable state. Random123, introduced in 2011, includes the Philox and Threefry families. A program can encode coordinates such as simulation replication, particle identifier, timestep, and local draw index into counters. This permits direct access to a particular pseudorandom value and maps naturally onto graphics processing units and other massively parallel hardware. Counter reuse under the same key repeats the corresponding output, so coordinate allocation is part of correctness.

Parallel execution also complicates reproducibility. A shared, thread-safe generator can avoid a race condition while still assigning different values to different tasks when scheduling changes. Per-task streams or counter-based addressing reduce this scheduling dependence. Nevertheless, identical random samples do not ensure bit-for-bit identical final results: floating-point reductions can change with evaluation order. Reproducible computation therefore separates random-input assignment from arithmetic determinism, task scheduling, software versions, and the mapping of logical work onto execution resources.

Applications, limitations, and neighboring methods

In Monte Carlo computation, pseudorandom samples approximate expectations and integrals. For independent samples X1,…,XNX_1,\ldots,X_N from a distribution of interest, an estimator often has the form

μ^N=1N∑i=1Nf(Xi).\hat{\mu}_N=\frac{1}{N}\sum_{i=1}^{N} f(X_i).

When the variance is finite, the ideal independent-sampling standard error decreases proportionally to N−1/2N^{-1/2}. PRNG output substitutes a deterministic sequence for those ideal samples, so uncertainty calculations rely on the generator behaving adequately for the estimator. Variance reduction methods deliberately introduce structure or dependence to improve efficiency; not every departure from independent sampling is undesirable.

Randomness also supports algorithms whose expected behavior is better or simpler than a deterministic alternative. Random pivot selection in quicksort, sampling in large datasets, and randomized search are examples. Here, the significance of predictability depends on the environment. A generator adequate for a closed numerical experiment may be inadequate when an adversary can choose inputs after observing its behavior. Hash-table defenses, for instance, can depend on secret randomization rather than merely on a sequence with an attractive histogram.

Machine-learning systems use pseudorandomness for parameter initialization, minibatch shuffling, dropout, data augmentation, and stochastic sampling. These uses differ in sensitivity. A small change in random initialization can alter an optimization trajectory, while a scheduling change may alter which worker consumes a random value. Reported experimental variation therefore reflects the interaction of random seeds with training procedures, data order, and numerical execution. In computer graphics and games, repeatability serves another purpose: a compact seed can recreate terrain, textures, particles, or an entire procedural environment without storing every generated detail.

A neighboring approach is the quasi-Monte Carlo method, which uses low-discrepancy point sets or sequences rather than attempting to imitate independent random draws. Sobol’ sequences are a prominent example. Their regularity is intentional: they aim to cover a multidimensional domain more evenly and can improve numerical integration for suitable problems. Randomized scrambling can combine such coverage with statistical error estimation. These methods should not be judged solely by tests designed to reject structured pseudorandom streams, because their objective is different.

Other apparent sources of randomness have distinct limitations. A hash function applied to a counter can form part of a generator, but security depends on the full construction and any secret inputs, not on the label “hash.” A chaotic mathematical system does not automatically yield a good digital generator: finite-precision implementation reduces it to a finite-state process that may have short cycles or bias. The choice between physical randomness, pseudorandom generation, and deliberately structured sampling is therefore governed by the required distribution, reproducibility, throughput, state constraints, and adversarial model.