the Miller-Rabin primality test
/ MILL-er RAH-bin /
Is a 600-digit number prime? Trying to divide it by every smaller number, or even by every number up to its square root, is utterly hopeless at that size. Miller-Rabin is a fast, randomized way to answer prime-or-not for huge numbers. It does not factor anything; instead it interrogates the number with a few random witnesses, and each witness either exposes the number as definitely composite or fails to — and enough failures make us confident the number is prime. It is the test that real cryptographic libraries use to generate the large primes RSA needs.
The test builds on Fermat's little theorem, which says that if n is prime then for any base a, a^(n-1) = 1 mod n. The strong (Miller-Rabin) version sharpens this. Write n - 1 = d * 2^s with d odd. If n is prime, then for a random base a, either a^d = 1 mod n, or one of a^d, a^(2d), a^(4d), ..., a^(2^(s-1) d) is equal to -1 mod n (these are the square roots of 1, and modulo a prime the only square roots of 1 are +1 and -1). If neither condition holds, then a is a witness proving n is composite — no honest prime could fail. The algorithm picks a random a, computes a^d mod n and repeatedly squares it (using fast modular exponentiation), and checks the pattern. If a witness fails to expose n, you try another random a. A trace flavor: for a true prime, every base obeys the pattern; for a composite like 561 (a Carmichael number that fools the plain Fermat test), most random bases catch it because the strong square-root condition is harder to fake.
Here is the honest core: Miller-Rabin is a Monte Carlo, one-sided-error test. If it ever reports composite, that is certain — a witness is a proof. If it reports probably prime, there is a small chance of error: for a composite number, a random base fails to be a witness with probability at most 1/4, so running k independent random bases drives the error below (1/4)^k, e.g. 40 rounds make a false prime astronomically unlikely. So you can make the error as tiny as you like at the cost of a few more rounds, but it is never exactly zero (unless you use a deterministic set of bases proven to work up to a known bound). Each round costs O(log n) modular multiplications, so the whole test is fast even for cryptographic sizes — which is exactly why it is the standard prime generator.
Test n=561 (= 3*11*17, composite). n-1 = 560 = 35 * 2^4, so d=35, s=4. Take base a=2: compute 2^35 mod 561, then square repeatedly. The sequence never hits 1 via a -1 step in the required pattern, so a=2 is a witness and Miller-Rabin correctly reports COMPOSITE — even though 561 passes the weaker plain Fermat test for some bases.
A witness proves compositeness for sure; passing k random bases leaves error below (1/4)^k.
Error is one-sided: 'composite' is certain, 'prime' is only probable — false-prime risk is at most (1/4)^k for k rounds, small but never exactly zero unless you use a proven deterministic base set.