Someone hands you a 300-digit number and asks a single question: is it prime? You could try dividing it by 2, then 3, then 5, then every number up to its square root… and you would still be grinding away long after the Sun burned out. And yet your web browser does this — for numbers this size — in a few milliseconds, thousands of times a day.

That speed is not a luxury; it is the practical engine of modern cryptography. To set up a secure connection, your computer must manufacture huge primes on demand — pluck a random 300-digit number, ask "prime?", and if not, try again. This only works because there is a way to tell whether a giant number is prime without ever factoring it, and far faster than finding its factors would take.

Trial division: correct but hopeless

The obvious test divides n by every prime up to \sqrt n. Why stop at the square root? Because if n = a \times b with both factors bigger than \sqrt n, their product would exceed n — so any composite must have a factor at or below \sqrt n. Find none, and n is prime.

Worked example. Is 97 prime? We need only test primes up to \sqrt{97} \approx 9.8, i.e. 2, 3, 5, 7. None divides 97 (it is odd, its digits sum to 16 so not a multiple of 3, it does not end in 0 or 5, and 97 = 7\times 13 + 6). Four checks — done — 97 is prime. Compare with 91: testing 7 gives 91 = 7 \times 13, so it falls at the third hurdle — composite.

This is perfectly correct and delightful for small numbers. But for a 300-digit n, \sqrt n still has 150 digits — more trial divisions than there are atoms in the observable universe. We need something cleverer than looking for factors at all.

The Fermat test: ask a prime's question

The clever move is to stop hunting for factors and instead test a property that every prime must have. Fermat's Little Theorem says that if p is prime then, for any base a not divisible by p,

So pick a base a and compute a^{n-1} \bmod n — quickly, using fast modular exponentiation, which needs only a few hundred multiplications even for a 300-digit exponent. Then read off the verdict:

• If the answer is not 1, then n is definitely composite — a watertight certificate of compositeness, and notice we found it without producing a single factor.
• If the answer is 1, then n is "probably prime" — it passed a test all primes pass, but so might the odd impostor.

Worked example. Test n = 15 with base a = 2: 2^{14} = 16384, and 16384 \bmod 15 = 4 \neq 1. The test fires: 15 is composite — and it told us so without ever revealing that 15 = 3 \times 5. That "detect without factoring" is the whole trick.

From "probably" to "almost surely"

There is a catch. A few rare composites pass the Fermat test for many bases — the Carmichael numbers, the smallest being 561 = 3\times 11\times 17. They satisfy a^{n-1}\equiv 1 for every base coprime to n, so they masquerade as primes no matter how many bases you throw at them. Rare, but real, and enough to make the plain Fermat test untrustworthy.

The fix is the Miller–Rabin test, a sharpened version that also looks for non-trivial square roots of 1 along the way — a check Carmichael numbers cannot survive. Every random base a composite survives cuts its chance of slipping through to at most 1/4. Run it with k independent random bases and the error probability is at most 4^{-k}.

Worked example. With k = 20 rounds the failure chance is at most 4^{-20} \approx 10^{-12} — less likely than your computer's memory being flipped by a passing cosmic ray during the calculation. That is why Miller–Rabin, not the plain Fermat test, is what actually generates the primes guarding your bank traffic.

This is a randomised algorithm — fast and astronomically reliable. And in 2002 a landmark result, the AKS test, proved that primality can even be decided in guaranteed \textit{polynomial time} with no randomness and no error at all — settling a long-open theoretical question. In practice, though, Miller–Rabin's speed wins, and it is what your devices actually run.