The Miller–Rabin Test
How we know a number is prime without dividing by zillions of smaller numbers — the clever test behind your prime.
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. So to test whether 97 is prime, you could try dividing 97 by 2, 3, 4, 5, … up to 96. If none of them divide evenly, 97 is prime. That’s called trial division, and for 97 it’s a bit tedious but doable.
Now imagine your candidate is a 128-bit number. That’s a number with about 39 decimal digits — bigger than a trillion trillion trillion. The number of possible divisors you’d have to try is astronomically large. Even the fastest computer in the world would need an absurd amount of time to check them all. So we need a method that doesn’t rely on trying every possible divisor. 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.