# What is a linear congruential generator?

> An LCG makes pseudorandom numbers with X(n+1) = (aX(n) + c) mod m. How to choose a, c and m for a full period, and what goes wrong with bad choices.

**Linear congruential generator**: A linear congruential generator produces pseudorandom numbers by the recurrence X(n+1) = (a X(n) + c) mod m for a fixed multiplier a, increment c and modulus m.

A **linear congruential generator (LCG)** is the classic pseudorandom number generator: pick a modulus m, a multiplier a and an increment c, and compute each number from the last as X(n+1) = (a X(n) + c) mod m. It is fast and tiny, and with good parameters it is fine for many simulations.

## Choosing the parameters

The sequence must eventually repeat, at most every m steps. Knuth gives exact conditions for the full period m when c is not zero: c and m share no factor, a - 1 is divisible by every prime factor of m, and by 4 if m is. He also defines **potency**, which rules out multipliers that pass that test but produce obviously patterned output.

## How to tell if it is any good

Full period is necessary, not sufficient. The rest of Volume 2's chapter 3 is about testing: empirical tests like the chi-square and gap tests, and the **spectral test**, which measures how the points (X(n), X(n+1), ...) fall on a few parallel planes. An LCG with a bad multiplier passes casual checks and fails the spectral test badly. Start at [§3.2.1](https://cracked.guide/guide/knuth-w048-1).

## Questions

### Should I use an LCG today?

For reproducible simulations or games it can be fine with well-tested parameters. Never for anything security related, and modern generators are usually a better default.

---

Source: https://cracked.guide/glossary/linear-congruential-generator
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.