Modern cryptography needs enormous primes — hundreds of digits long. We obviously cannot find them by factoring (that is far too slow) or by sieving (the numbers are astronomically large). The surprising resolution: we can check whether a giant number is prime without ever factoring it, and far faster than finding its factors.

Trial division: correct but hopeless

The obvious test divides n by every prime up to \sqrt n. It is perfectly correct, and fine for small numbers. But for a 300-digit number, \sqrt n still has 150 digits — more trial divisions than there are atoms in the universe. We need something cleverer.

The Fermat test: ask a prime's question

Instead of looking for factors, we test a property that all primes share. 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 — see fast modular exponentiation). If the answer is not 1, then n is definitely composite — a watertight certificate of compositeness, with no factor ever found. If the answer is 1, then n is "probably prime".

From "probably" to "almost surely"

The catch: a few rare composites pass the Fermat test for many bases (the Carmichael numbers, like 561). The fix is the Miller–Rabin test, a sharpened version: each random base it survives cuts the chance that a composite slips through to at most 1/4. Run it with k independent bases and the error probability is at most 4^{-k} — vanishingly small.

This is a randomised algorithm — fast and astronomically reliable. (A deterministic polynomial-time test, AKS, was found in 2002, settling the theory; in practice Miller–Rabin is what generates the primes guarding your bank traffic.)