Testing for Primes

Liars, Carmichael numbers and Miller–Rabin

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Fermat test: if $a^{n-1} \not\equiv 1 \pmod n$, then $n$ is composite.
• Pseudoprimes and Carmichael numbers (561, 1105, 1729) can fool it.
• Miller–Rabin also checks square roots of 1, so each base catches a composite with probability at least 3/4.

Steps

1. Trial division
2. Fermat liars
3. Carmichael numbers
4. Korselt’s recipe
5. A fake square root
6. Finding an RSA prime