Beyond Fermat
The simple Fermat test is fooled by certain composites. Miller Rabin strengthens it by looking not only at the final power but at the sequence of squarings that produced it, catching numbers that hide as primes.
How it probes
Write the candidate minus one as an odd part times a power of two. For a chosen base:
- Raise the base to the odd part under the modulus.
- Square it repeatedly, the number of times set by that power of two.
- A genuine prime must reach one only through the value one or through the modulus minus one along the way.
If the sequence reaches one without first passing through the modulus minus one, a forbidden square root of one has appeared, proving the candidate composite.
Confidence
Each base either proves compositeness or leaves the candidate a probable prime. Trying several well chosen bases drives the chance of error very low, and fixed base sets are known to be exact below large bounds.
Key idea
Miller Rabin inspects the chain of repeated squarings for a base and declares a number composite when one appears without a preceding modulus minus one, giving a fast test that is exact for fixed bases below known bounds.