Nineteen thousand bits of state

The three rungs below establish that a linear congruential generator has a lattice defect bounded by its modulus, and can be solved from three outputs. Two responses are available: build something non-linear and slow, which is the previous rung, or keep the linearity and make the state enormous, which is what almost every scientific library actually does. The second sounds like an evasion and is not: the bound the first rung proves is a bound in terms of the state size, so enlarging the state is attacking the bound at exactly the place it is stated.

The second response deserves a rung of its own because it is a genuine engineering answer to a mathematical bound, and because the properties it achieves are proved rather than assumed.

Linearity over two elements #

The Mersenne twister’s state is 624 words of 32 bits — 19,937 bits after one bit is discarded — and its step is a linear map over the field with two elements: a shift, a mask and an exclusive-or.

Working over that field rather than modulo a large number changes what can be proved.

The period is a question about a polynomial. A linear recurrence over a finite field has a characteristic polynomial, and the period is maximal exactly when that polynomial is primitive — meaning its roots generate the multiplicative group of the extension field. For a state of $n$ bits the maximal period is $2^n - 1$, and checking primitivity requires knowing the factorisation of $2^n - 1$.

That is where the Mersenne prime comes in. $2^{19937} - 1$ is prime, which makes the primitivity test trivial: every non-constant polynomial of the right degree with a non-trivial root generates everything, because the group has prime order and no proper subgroups. Choosing the state size to make a Mersenne prime is the whole reason for the number, and for the generator’s name.

So the period is $2^{19937} - 1$, proved, which is about $10^{6001}$ — more than enough that no computation will ever wrap.

The proof deserves one more sentence because it is short and its shortness is the design’s payoff. If $2^n - 1$ is prime, the multiplicative group of the field with $2^n$ elements has prime order, so every element other than the identity generates it. A polynomial of degree $n$ that is irreducible therefore has a root generating the whole group, which is what primitive means. So irreducibility implies primitivity when the exponent gives a Mersenne prime, and irreducibility is a cheap test.

Equidistribution, proved #

The second designed property is the one the hero figure measures on a small analogue.

A generator is $k$-dimensionally equidistributed to $v$ bits when every one of the $2^{kv}$ patterns formed by the top $v$ bits of $k$ consecutive outputs occurs equally often over a full period. That is a statement about the whole period, it is exact, and it is a counting fact rather than a statistic — no sample is drawn and no confidence interval appears anywhere in it.

For a linear recurrence over the two-element field it is decidable, by linear algebra: the map from a state to the concatenation of $k \times v$ output bits is linear, so the patterns are equidistributed exactly when that map is onto, which is a rank computation.

The decidability is the whole reason to work over that field. Over the integers modulo a large number the corresponding question is about a lattice and has no exact answer short of a shortest-vector computation; over the two-element field it is the rank of a matrix, computable exactly and in time cubic in the state size. Choosing an algebraic setting in which the design criterion is a rank rather than a search is what makes a large generator provable at all, and it is the decision the rest of the design follows from.

The Mersenne twister is 623-dimensionally equidistributed at 32 bits. That means six hundred and twenty-three consecutive outputs, at full precision, cover every combination equally often. Compared against the lattice bound of the first rung — which for a modulus of $2^{32}$ gives a few thousand hyperplanes in ten dimensions — the difference is not a matter of degree.

Why a big state defeats the bound #

The lattice bound of the first rung is not evaded by cleverness; it is evaded by making its parameter large.

A generator whose state is a single number modulo $m$ has an annihilating lattice of determinant $m$, and Minkowski’s theorem then bounds the shortest vector by roughly $m^{1/d}$ in dimension $d$. The bound is a function of the state size and of nothing else.

A generator with a state of $n$ bits has, in the corresponding sense, $m = 2^n$, so the bound in dimension $d$ is $2^{n/d}$. At $n = 19937$ and $d = 100$ that is $2^{199}$, which is not a constraint on anything.

So the answer to “how good can a linear generator be” is: as good as its state is large. The classical generators were bad because a state of thirty-two bits was what a machine could afford, and the constraint disappeared with memory.

That figure is worth reading as the historical situation rather than as a technique. When a generator’s whole state was one machine word, the period was a scarce resource: four billion values sounds ample and is exhausted by a simulation drawing a million numbers a second in an hour. Every design decision of the classical era was made under that pressure.

The Mersenne twister’s period is $2^{19937} - 1$, and no argument about exhausting it is possible. A machine drawing a billion numbers a second since the beginning of the universe would have used a number of values with nineteen digits, against a period with six thousand. The resource stopped being scarce, and the design freedom that released is what the rest of this rung is about.

What it does not have #

It is not cryptographically strong, and is not offered as such. The recurrence is linear over the two-element field, so observing 624 outputs gives 19,937 linear equations in the state’s 19,937 unknowns, and Gaussian elimination recovers it. That is a larger computation than the three-output solve of the previous rung but one and it is the same computation.

It fails some statistical tests. The linear structure shows up in tests specifically designed to look for it — the binary-rank tests and the linear-complexity tests of the standard batteries — and the generator fails them by construction rather than by accident. Whether that matters depends on whether a simulation’s answer depends on linear relations among its random bits, and usually it does not; the cases where it does are the ones documented above, and they are hard to predict in advance, which is the honest position.

It uses two and a half kilobytes of state, which is not free. Every instance of the generator carries 624 words, so a program with a generator per thread pays for each, and the state does not fit in a processor’s fastest cache alongside anything else. The modern smaller-state generators were motivated partly by this: a 256-bit state fits in registers and a 20,000-bit one does not, and on current hardware the difference in speed is substantial.

And it is slow to recover from a bad seed. With a state of that size, a seed of a few bits leaves most of the state zero, and the recurrence takes a long time to mix it in. Early users reported exactly this and the initialisation routine was revised; it is a design defect in the seeding rather than in the recurrence, and it is the standard kind.

The contrast between the two figures above is the clearest statement of what a large state does and does not buy. Against a bound that scales with the state, it wins completely. Against an attack whose cost scales with the state, it changes a three-number computation into a twenty-thousand-equation one — which is minutes rather than microseconds, and is no protection at all against anybody who wants it.

What replaced it #

The Mersenne twister was published in 1998 and is still the default in a great many libraries. The generators designed since have taken a different route, and comparing them is instructive.

Smaller states, better mixing. The xoshiro and PCG families use states of 128 or 256 bits and add a non-linear output transformation — a multiplication, or a rotation by a state-dependent amount. That breaks the linearity that the rank tests detect, at the cost of losing the exact equidistribution proof.

So the trade has reversed. The Mersenne twister offers proved properties and a detectable linear structure; the modern generators offer no proof and no detectable structure. Which is preferred depends on whether one values a theorem about a property nobody’s simulation depends on, or the absence of a defect nobody has found.

It is worth being clear that this is a genuine disagreement rather than a settled question. The case for the twister is that equidistribution to hundreds of dimensions is exactly the property a high-dimensional integration wants, and it is proved. The case against is that the linear structure is real, has been demonstrated to affect certain physical simulations — Ising model studies in the 1990s produced wrong answers with linear generators and right ones with others — and the equidistribution theorem did not prevent it. A proved property is only worth what the property is worth, and choosing which properties to prove is the design decision underneath all of this.

Neither family is cryptographic, and both say so plainly in their own documentation, which is a change of practice worth noting: the classical generators said nothing, and the failures listed on the rung below happened to people who had no reason to suspect a difference existed. The separation between the two purposes, which the previous rungs argue for, is now standard practice.

The pattern in the design #

Three choices recur across all the good generators and are worth naming.

Pick a structure with a theory. Linear recurrences over finite fields have a complete theory of periods, and it is the reason the Mersenne twister’s period is proved rather than measured. A generator built from ad hoc operations has no such theory, and its period is whatever a search finds — which for a large state cannot be searched for at all, so the period becomes unknown rather than merely unproved.

Choose the parameters to make the theory cheap. The Mersenne prime is chosen so that the primitivity test is trivial. That is an engineering decision inside a mathematical constraint, and it is why the state size is a strange number rather than a round one. A designer who insisted on a state of exactly twenty thousand bits would have had to factor a six-thousand-digit number to prove anything, and would have shipped a generator with an unproved period.

And add a non-linear output only at the end. This is the one that is easy to get wrong in the other direction. The recurrence must stay linear to keep the theory; the output can be transformed arbitrarily, and a well-chosen transformation destroys the detectable structure without touching the period. That is exactly what the modern generators do and what the Mersenne twister’s tempering step does weakly — its tempering is itself linear over the two-element field, which preserves the equidistribution proof and preserves the solvability along with it. A non-linear tempering would break the second and forfeit the first, and choosing which to keep is the whole disagreement of the previous section.

The Mersenne prime, and why it was worth waiting for #

The choice of state size is the most peculiar design decision in the generator and the most instructive.

Establishing that a linear recurrence has maximal period means establishing that its characteristic polynomial is primitive over the two-element field. The standard test asks, for every prime factor $r$ of $2^n - 1$, whether a certain power of the polynomial’s root is one. So the test needs the factorisation of $2^n - 1$ — and factoring a number with six thousand digits is not something anybody does.

Unless $2^n - 1$ is prime, in which case there is one factor, the test collapses, and primitivity is checkable in a moment.

Numbers of the form $2^n - 1$ that are prime are the Mersenne primes, they are rare, and $19937$ is one of the exponents that produces one. So the state size was chosen from a list of known Mersenne exponents, and the number in the generator’s name is a prime exponent rather than anything about hardware.

That is an unusually direct dependence of an engineering artefact on a piece of pure number theory. The search for Mersenne primes has been going on since the seventeenth century, mostly for its own sake and later as a benchmark for computers; one of its outputs is the parameter of the generator that most scientific software uses. Perfect numbers are the classical reason to care about them and this is the modern one.

What the pictures cannot show #

The register drawn has ten bits and the generator has nineteen thousand. Everything in the figures is a small analogue whose properties can be counted; the properties of the real generator are established by rank computations over a nineteen-thousand-dimensional space and have no exhibit.

Equidistribution to six hundred and twenty-three dimensions cannot be drawn in any sense. The figures verify two, three and five. The claim is about a number of dimensions larger than the number of atoms anybody would use to draw one.

The failure modes are invisible by construction. A generator’s defect shows up as a wrong answer in a simulation that happens to depend on the structure, and there is no picture of that: the simulation looks like a simulation, and the answer looks like an answer. Every documented case in the literature was found by running the same computation with two generators and getting two results.

And the period is a number with six thousand digits. No figure can indicate the difference between that and a period of a million; both are “it does not repeat” as far as any drawing goes, and the difference between them is the whole point of the design.

Where the ladder goes next #

This rung closes the ladder’s first pass: the lattice defect measured, the predictability demonstrated, the cryptographic repair described, and the engineering answer set out here.

Named here as debts. Tempering — the output transformation that improves a linear generator’s equidistribution without changing its period — which every generator here has and none of the figures draws. And testing batteries themselves, which is how the modern generators are actually evaluated in the absence of proofs, and which is a subject with its own methodology.

Sideways, the polynomial whose primitivity decides the period is the characteristic polynomial of a linear map over a different field, the counting of patterns is a generating function’s kind of question, and the primes that make the arithmetic cheap are Mersenne’s.

What is worth carrying away #

A mathematical bound on a construction is often a bound in terms of one parameter, and the engineering answer is to make that parameter large rather than to be clever.

Every defect of a linear congruential generator is bounded by its state size. Thirty years of work on better multipliers produced marginal gains; increasing the state from thirty-two bits to nineteen thousand made the bound irrelevant in one step. The bound was never about linearity — it was about memory, and the constraint that produced it stopped applying.

The habit worth taking is to read a bound’s parameters before trying to beat it. If the bound depends on a resource, spending more of the resource is the answer; if it depends on the structure, only a different structure will do — and telling the two cases apart is the whole of the decision.