Linear Congruential Generators vs. Modern CSPRNGs: Why the Old Algorithm Was Predictable
A linear congruential generator produces its next value as Xₙ₊₁ = (aXₙ + c) mod m — a fixed formula applied to the previous output — so once an observer recovers the constants a, c, and m from a handful of outputs, every future value becomes fully predictable; a modern cryptographically secure generator is deliberately built so that recovering its internal state from its outputs is computationally infeasible.
A worked example with numbers
Consider a small illustrative LCG with a = 5, c = 1, m = 16, and a starting seed of 0. Applying Xₙ₊₁ = (5·Xₙ + 1) mod 16 repeatedly produces the sequence 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5, 10, 3, 0, and then it repeats exactly from the start: 1, 6, 15, 12, and so on. That repeat after exactly 16 outputs is the generator’s period, and it is no coincidence that it equals m — a well-constructed LCG with these particular parameters visits every value from 0 to m−1 exactly once before repeating, a design property, not a flaw. The flaw is different: once an observer has recorded even a short run of consecutive outputs, the same fixed formula that generated them can be solved for a, c, and m, after which every future output — and every past one — is known exactly.
How to set the rule before the result
Real-world LCGs used historically in software libraries typically use a much larger modulus, commonly m = 2³¹ or m = 2³², to make the output range large enough for practical use; a classic example uses a = 1,103,515,245 and c = 12,345 with m = 2³¹, generating the sequence 1,103,527,590, then 377,401,575, and so on from a seed of 1. Anyone building or auditing a generator can check for this weakness directly: take three or four consecutive outputs, and attempt to solve the recurrence for a, c, and m using standard linear-algebra techniques. If that recovery succeeds, the generator is an LCG or an equivalent fixed-recurrence design and should not be used anywhere prediction would matter, regardless of how statistically balanced its output looks on a chi-square or NIST-style test.
Common mistakes that change the odds or the process
A common mistake is assuming a generator that passes a statistical balance test, such as the frequency and runs tests described in NIST’s SP 800-22 battery, is automatically safe to use for anything — an LCG can be constructed to pass those tests comfortably while remaining fully predictable once a handful of outputs leak, because passing a balance test and resisting prediction are different properties entirely. A second mistake is assuming every JavaScript engine’s Math.random() is secretly an LCG under the hood; browser vendors have used a variety of algorithms over the years, and the specification deliberately does not mandate one, which is itself part of why Math.random() is documented as unsuitable for anything requiring unpredictability. A third mistake is assuming a long period, such as the 2³¹ period of the classic example above, provides any protection against prediction — period length only measures how long a generator can run before its output repeats exactly; it says nothing about how quickly its internal state can be recovered from watching its output.
Where this method stops being appropriate
This predictability concern applies specifically to generators with a fixed, invertible recurrence relation and no external entropy reseeding; it does not describe every algorithmic (non-hardware) generator equally. A modern CSPRNG, such as the one behind a browser’s crypto.getRandomValues(), is also algorithmic rather than physical, but it is explicitly designed so that recovering its internal state from its output is computationally infeasible even with far more observed outputs than a simple LCG would need. Nothing here says an LCG is unsuitable for every use — a simulation, a procedurally generated game level, or a Monte Carlo statistical experiment often has no adversary trying to predict the sequence, and a fast, reproducible LCG can be the right tool for exactly that kind of task.
How the random source fits into the rule
MDN’s Math.random reference documents that Math.random() is not specified to use any particular algorithm and states plainly that it must not be used where cryptographic security matters; NIST SP 800-90A documents the design requirements a modern deterministic random bit generator must meet, including resistance to state recovery from observed output — the exact property a plain LCG lacks.
Reading the recurrence formula piece by piece
| Symbol | Role | Small example |
|---|---|---|
| Xₙ | Current state / output | starts at seed 0 |
| a | Multiplier | 5 |
| c | Increment | 1 |
| m | Modulus (also the maximum possible period) | 16 |
| Xₙ₊₁ | Next output | (5·Xₙ + 1) mod 16 |
Every value in the sequence is produced from exactly one previous value and three fixed constants — there is no hidden extra randomness injected at each step, which is precisely why the whole future sequence collapses to “solve for three numbers” once enough outputs are visible.
A second case: what four observed outputs reveal
Suppose an attacker observes four consecutive outputs from an unknown LCG: 1, 6, 15, 12. Because each output relates to the last by the same fixed formula, the differences between consecutive pairs — 6−1=5, 15−6=9, 12−15=−3 — combined with the known small modulus, are enough information to solve for a, c, and m using standard integer linear algebra, recovering exactly a=5, c=1, m=16 in this case. With those three constants recovered, every output that generator will ever produce, starting from any seed, is now computable in advance — the four leaked numbers were enough to break the entire future sequence, not just predict the fifth one.
Why period length is not the same as unpredictability
A frequent misunderstanding treats a generator’s period — how many outputs it produces before repeating — as a proxy for its quality. The classic 2³¹-modulus example above has a period in the billions, far longer than almost any practical use would ever exhaust, and it is still fully predictable from a handful of leaked outputs, because period length describes repetition, not recoverability. A modern CSPRNG can have a comparably long or even shorter practical output window before reseeding and still be far more resistant to prediction, because its security comes from the computational difficulty of inverting its internal function, not from how rarely it repeats itself.
A well-documented historical case is IBM’s RANDU generator, a linear congruential generator widely distributed in the 1960s and 1970s with a = 65,539 and m = 2³¹. RANDU passed many contemporaneous statistical checks, yet plotting consecutive output triples as points in three-dimensional space revealed they all fell on just 15 parallel planes rather than filling the space evenly — a structural flaw invisible to a one-dimensional frequency test but glaring once the right kind of test was applied. RANDU’s downfall illustrates a point beyond prediction alone: even the specific statistical tests a generator is checked against matter, since a generator can look flawless under one test and badly structured under another.