The Miller–Rabin Test

When we go hunting for your prime number, we have to answer one question over and over, like a bouncer at a very exclusive club: Is this number prime? For small numbers — say, 7 or 23 — you can check by hand. For the kind of huge 128-bit numbers we use here, “try dividing by everything smaller” is not a plan. It’s a recipe for your computer to take a very long nap. So we use a smarter tool: the Miller–Rabin primality test. It’s the same idea that keeps your bank and your passwords safe. Let’s see how it works — and why you can trust it.

The problem: when “just check” doesn’t work

You probably learned that a prime number is one that’s only divisible by 1 and itself. To test whether a small number like 97 is prime, the textbook approach is trial division: try dividing it by smaller numbers. If none divide evenly, 97 is prime.

If you remember a bit of algebra, you know you don’t even have to test every number up to 96. First, you only need to test primes — if 2 doesn’t divide 97, multiples like 4, 6, or 8 won’t either. Second, you can stop once you reach the square root of 97 (√97 ≈ 9.8). If 97 had two factors, they couldn’t both be bigger than 9.8 (otherwise 11 × 11 = 121, already overshooting 97). So you only have to check four primes: 2, 3, 5, and 7. Four quick divisions, and presto: 97 is definitely prime.

That feels manageable. But now imagine your candidate is a 128-bit number — the kind we use for your personalized prime. That’s a number with roughly 39 decimal digits (bigger than a trillion trillion trillion).

Even using our clever square-root trick, the square root of a 128-bit number is a 64-bit number — around 18 quintillion. And how many primes live between 2 and 18 quintillion? Roughly 400 quadrillion.

Even if the fastest supercomputer could test one billion primes every single second without breaking a sweat, checking just one candidate number would take over 13 years. And when hunting for your prime, we have to test dozens of candidates before finding the winner. You’d be waiting until your grandchildren were grown just to get your prime.

So trial division — even with all its shortcuts — is a non-starter. We need a method that doesn’t rely on trying divisors at all. We need a clever method.

Enter the Miller–Rabin test. It’s named after Gary Miller (who came up with a deterministic version in the 1970s) and Michael Rabin (who turned it into the practical, probabilistic test we use today). They asked: what if, instead of checking every divisor, we could ask a few sharp questions that almost always catch a number that isn’t prime? (Mathematicians love that kind of question. It’s how we get out of doing brute-force work.) If a number passes those questions, we can be staggeringly confident it’s prime — without ever dividing by “zillions” of smaller numbers.

The big idea: liars and witnesses

Here’s the beautiful idea. If a number is composite (not prime), then there’s a hidden structure: it has factors. The test doesn’t look for the factors directly. Instead, it does a special kind of calculation that reacts to that structure. For most composite numbers, if you run this calculation with a random “base” number (like 2, 3, 5, 7, …), the result gives the game away — we get a kind of “witness” that the number is composite. So we say: the base witnesses that the number is composite.

Every now and then, a composite number might pass one particular base — we call that a “liar” for that base. It’s lying to us, pretending to look prime. But here’s the key: liars are rare. For any given composite number, at least three-quarters of the possible bases will tell the truth and witness that it’s composite. So if we try not one base but many — say, 16 small primes — the chance that a composite number slips past all of them is vanishingly small.

Think of it like a lie-detector that asks 16 independent questions. We’re not being mean — we’re just doing our job. If you’re telling the truth (the number really is prime), you’ll pass all 16. If you’re lying (the number is composite), at least one of those questions will usually catch you. We’re not proving primality in the old-fashioned sense; we’re making it astronomically unlikely that a composite could sneak through.

What we actually do (without the scary symbols)

The calculation itself uses something called modular exponentiation. That’s a fancy phrase for: take a number (the base), raise it to a certain power, and then look at the remainder when you divide that result by your candidate number.

You’ve done “remainder” since elementary school: 17 ÷ 5 is 3 with remainder 2. So we say “17 mod 5 = 2.” In the test, we do similar things but with huge powers — like “what is 2^(something) mod (your candidate)?” We don’t actually compute the full giant number; there are fast algorithms (square-and-multiply) that only ever work with remainders, so the calculation stays feasible even for 128-bit candidates.

For each base (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53), we run this kind of check. If any base “witnesses” compositeness — i.e., the result of the calculation fits a precise pattern that only composites can produce — we immediately know the candidate is not prime and we throw it away. If the candidate passes all 16 bases, we treat it as prime. In practice, we’re as confident as we need to be.

How sure are we?

If a number passes all 16 tests, the chance that it’s actually not prime is astronomically small — far less than 1 in a billion squared. To put that in perspective: you’re more likely to be struck by lightning several times in one year than to hit a composite number that slips past 16 rounds of Miller–Rabin. Cryptography and security standards (the same math that protects your credit card and your email) rely on exactly this idea: “probable prime” with such a tiny error rate that the whole world treats it as prime.

So when we say your number passed the Miller–Rabin test, we mean: we ran it through 16 independent checks with 16 different bases, and it passed every single one. Your prime is the first number we found that passed — and it’s yours for good. We didn’t have to divide by zillions of smaller numbers; we just asked 16 sharp questions, and your number told the truth every time.

The “From Name to Prime & Back” Series

Follow the complete journey of how a name transforms into a prime number and back:

First, We Tidy Your Name — Standardizing characters, accents, and spaces.
Packing Your Name Into Fewer Bits — How Huffman compression makes the puzzle fit.
Your Tiny Key and the Number Lock — Feistel ciphers and why 3-character keys are fun.
Prime Hunting With Tiny Tweaks — Wiggling nonces and the Miller–Rabin primality test.
How Decoding Works (Backwards Magic) — Running the pipeline in reverse to recover your name.
Share the Prime, Protect the Key — Keeping your name private until you choose to reveal it.

Companion Deep Dives:

Huffman Coding: Squeezing Names into Fewer Bits — The mathematics of optimal binary prefix trees.
The Miller–Rabin Test — (You are here) How we verify primality in microseconds without trial division.
Organic, Artisanal Math — Why deterministic algorithms beat AI hallucinations.