LCG

Linear congruential generator (LCG) is a simple pseudorandom number generator used in computing. It produces a sequence of integers by the recurrence X_{n+1} = (a X_n + c) mod m, where m is the modulus, a is the multiplier, c is the increment, and X_0 is the seed. Each X_n lies in the range 0 to m−1. To obtain a real-valued sequence in the unit interval, X_n is often divided by m.

For the generator to have a full period of m, certain conditions must hold: c and m are coprime; a−1 is a multiple of every prime factor of m; and if m is divisible by 4, then a ≡ 1 (mod 4). When these conditions are satisfied, the sequence can cycle through all possible values before repeating.

Variants of LCG include the mixed or additive form (c ≠ 0) and the multiplicative form (c = 0). A well-known multiplicative variant is the Park–Miller (also called the minimal standard) generator with a = 16807 and m = 2^31 − 1. LCG parameters are often chosen to balance speed, memory usage, and statistical quality.

Properties and limitations: LCGs are fast and memory-efficient, making them suitable for simple simulations and games. However, they exhibit lattice structures in higher dimensions, which can lead to detectable correlations. They are also predictably deterministic if the modulus, multiplier, increment, and seed are known, so they are not cryptographically secure.

Usage: LCGs have historically been used in many programming languages’ standard libraries (for example, simple rand functions) and in early simulations. Modern systems frequently use more robust generators, but LCGs remain a foundational concept in the study of pseudorandom number generation.