How Random Is Random? A Playable Tour of the Mersenne Twister

One of the first bugs I ran into in bug bounty had nothing magic about it. A password-reset code was generated with the same kind of random() a game would use to roll loot. Random enough to look safe, predictable enough not to be.

That bug stuck with me because it raises a question that sounds silly until you try to answer it: how does a computer, a machine that does exactly what it's told, come up with something random?

Short answer: it doesn't. It fakes it. The long answer is a lot more fun, and every figure below runs the real algorithm in your browser, so you can poke at it.

First, a test

Here are two fields of 90 dots. One of them was placed by a random number generator. The other one wasn't.

If you picked the tidy one, welcome to being human. We expect randomness to look evenly spread, with no clumps and no gaps. Real randomness is lumpy: some dots land on top of each other and big patches stay empty, because every dot is placed without caring where the others went.

Keep that in mind. "Looks random" and "is random" are different things, and that gap is where everything interesting in this post lives.

Computers can't flip coins: pseudo-random numbers and seeds

A CPU is deterministic: same input, same output, every time. So instead of random numbers, programs use pseudo-random ones: a formula that takes a number (the seed) and produces a long sequence that looks random.

Same seed, same sequence. Always.

That sounds like a weakness, but most of the time it's a feature. It's how a game can replay a match from a seed, how a simulation can be re-run exactly, and how a procedurally generated world looks the same on your machine and mine. The seed is the whole world, compressed into one number.

So the real question becomes: what formula turns one number into a sequence that looks random?

Attempt #1: middle-square (1949)

John von Neumann needed lots of random digits for early computer simulations, and he proposed something beautifully simple: take a 4-digit number, square it, and keep the middle four digits. That's your next number. Repeat.

Try a few seeds. It starts out looking random, then it either collapses to zero or falls into a short loop and stays there forever. With 2026 as the seed it gets 97 numbers in before it starts repeating 4100 → 8100 → 6100 → 2100.

Von Neumann knew the method was weak. When he presented it, he also said one of the best lines in computing:

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.

(He used it anyway. It was fast, and when it broke, it broke in obvious ways he could spot.)

Attempt #2: RANDU and its 15 planes

Next came linear congruential generators: multiply, add, take the remainder.

x = (a * x + c) % m

Pick a, c and m well and you get long, decent-looking sequences. Pick them badly and you get RANDU, IBM's generator from the 1960s, used for years in scientific code:

x = (65539 * x) % 2 ** 31

It passes a quick look. The numbers seem spread out, no obvious pattern. Now take three consecutive outputs and use them as the coordinates of a point in a cube. Do that 3,000 times:

From almost any angle: fog. From one angle: every point sits on one of just 15 planes. In a truly random cloud, points can be anywhere. Here, most of the cube is guaranteed to be empty.

Why? Because 65539 = 2¹⁶ + 3, and with a bit of algebra that choice means every output is tied to the previous two:

x[k + 2] = (6 * x[k + 1] - 9 * x[k]) % 2 ** 31

The third number is never free. Any simulation that drew random points in 3D with RANDU was sampling a set of slices, not a volume. This is the lesson to remember: a generator can pass every test you happen to look at and still have structure hiding in a dimension you didn't check.

How the Mersenne Twister works

In 1998, Makoto Matsumoto and Takuji Nishimura published the generator that would become the default almost everywhere: Python's random, Ruby's Random, PHP's mt_rand, R's default, and C++'s std::mt19937.

Three ideas make it work.

1. A huge state. RANDU remembers one number. The Mersenne Twister remembers 624 of them: 624 × 32 bits, almost 20,000 bits of state. Each call to random() reads the next word from that pile.

2. The twist. When all 624 words are used up, it rebuilds the whole pile. Each new word is made from three old ones: the top bit of word i, the low 31 bits of word i + 1, and word i + 397, mixed with a shift, an XOR and a magic constant.

Seed it with 5489 (C++'s default) and the first number it gives you is 3499211612. Same on your machine, mine, and every correct implementation ever written. That's the seed thing again.

3. Tempering. The raw words in the state have some statistical patterns, so before a word leaves the generator, four shift-and-XOR steps scramble its bits:

The payoff is the name. The sequence only repeats after 2¹⁹⁹³⁷ − 1 numbers. That number is a Mersenne prime (a prime of the form 2ⁿ − 1, named after the friar Marin Mersenne), and written out it has 6,002 digits. You'll never see it repeat. Neither will the universe.

It also has none of RANDU's problem. Its outputs are evenly spread in up to 623 dimensions at once, which is why the RANDU cube above turns back into fog when you switch to the Twister.

The whole core fits on one screen:

// The twist: rebuild all 624 words.
for (let i = 0; i < 624; i++) {
  const y = (mt[i] & 0x80000000) | (mt[(i + 1) % 624] & 0x7fffffff);
  mt[i] = mt[(i + 397) % 624] ^ (y >>> 1) ^ (y & 1 ? 0x9908b0df : 0);
}
 
// Tempering: scramble one word on its way out.
function temper(y: number) {
  y ^= y >>> 11;
  y ^= (y << 7) & 0x9d2c5680;
  y ^= (y << 15) & 0xefc60000;
  y ^= y >>> 18;
  return y >>> 0;
}

Fast, a period no one will ever reach, great statistics. Problem solved?

Plot twist: predicting the Mersenne Twister from 624 outputs

Look at the end of the tempering figure again. I ran it backwards. Every tempering step can be undone, so from one output you can recover the exact state word it came from.

And the generator is nothing but its 624 words of state. Collect 624 consecutive outputs, untemper each one, and you have a perfect copy of the generator. From then on you know every number it will ever produce.

Let's try it. This pretend server hands out password-reset tokens straight from a Mersenne Twister with a secret seed:

No brute force and no guessing the seed: 624 tokens and some bit-flipping. That's the bug from the beginning of this post, and why it's a real bug: if an attacker can see enough outputs, they can predict the reset code meant for someone else's account.

The Mersenne Twister wasn't badly designed. It was designed to be statistically random (great for simulations, games and sampling), not unpredictable. Those are different jobs. Python's documentation says so directly: its random module should not be used for security, and it points you to secrets.

(In case you're wondering about JavaScript: V8's Math.random() isn't a Mersenne Twister. It has used xorshift128+ since 2015. It isn't meant to be unpredictable either; it just takes a different trick to predict.)

Where real unpredictability comes from: CSPRNGs

From things a formula can't know: timing jitter in hardware, interrupts, noise in the CPU's circuits. Your operating system collects that kind of entropy into a pool and feeds it into a cryptographically secure generator (a CSPRNG). It's designed so that even after seeing a million outputs, you can't predict the next one or work back to the earlier ones.

Some companies go further. Cloudflare famously points a camera at a wall of lava lamps in its office lobby and mixes the footage into its randomness, alongside other sources. It sounds like a joke, but it's real.

You don't need lava lamps. You already have a CSPRNG one call away:

// Browser and Node
crypto.getRandomValues(new Uint32Array(1));
crypto.randomUUID();

# Python
import secrets
secrets.token_urlsafe(32)

The cheat sheet

So, how random is random? On a computer, almost never truly. It's a formula good enough to fool a test, or the eye, or years of scientific code (sorry, RANDU). The useful question isn't "is this random?" It's "random enough for whom?" For a dice roll, a twister is perfect. For someone trying to guess your reset code, only real unpredictability will do.

Quick answers

Is the Mersenne Twister cryptographically secure? No. Each output is a reversible scramble of one word of its state, so 624 consecutive 32-bit outputs are enough to rebuild the generator and predict every value after them. For tokens, keys and reset codes, use a CSPRNG such as crypto.getRandomValues or Python's secrets.

Why is it called the Mersenne Twister? Its period, 2¹⁹⁹³⁷ − 1, is a Mersenne prime. "Twister" comes from the twist step that rebuilds its 624-word state; it's a variant of an earlier family of generators called twisted GFSR.

Who uses it? Python's random, Ruby's Random, PHP's mt_rand, R's default generator and C++'s std::mt19937 are all MT19937.

What does JavaScript's Math.random() use? It depends on the engine. V8 (Chrome, Node.js) has used xorshift128+ since 2015. It isn't cryptographically secure either.

What was wrong with RANDU? Its multiplier, 65539, is 2¹⁶ + 3. That makes every output a fixed combination of the previous two (x[k+2] = 6·x[k+1] − 9·x[k] mod 2³¹), so consecutive triples fall on just 15 planes.

Sources

• Makoto Matsumoto and Takuji Nishimura, Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation 8(1), 1998.
• Python documentation, random: Generate pseudo-random numbers.
• V8 blog, There's Math.random(), and then there's Math.random() (2015).
• Cloudflare, Randomness 101: LavaRand in Production (2017).
• MDN, Crypto.getRandomValues().
• Wikipedia, RANDU and Middle-square method.

The figures run a TypeScript MT19937 that matches the reference implementation: seeded with 5489, its first output is 3499211612 and its 10,000th is 4123659995, the value the C++ standard requires of std::mt19937.