Sign in to watch this lesson
Advanced - Number Theory · 4:38
Primality Tests: Trial Division, Fermat, Miller–Rabin
Trial division needs about 10^9 steps for one number near 10^18, so big numbers are tested with modular powers instead. The Fermat test proves compositeness when a^(n−1) ≢ 1 but is fooled by Carmichael numbers such as 561 for every coprime base; Miller–Rabin also checks that the squaring walk from a^d reaches −1, leaving at most a quarter of bases as liars, and seven fixed bases make it exact for all 64-bit n.
You will learn
- Explain why trial division is too slow for 64-bit inputs and why a^(n−1) ≢ 1 (mod n) proves n composite
- Explain why Carmichael numbers defeat the Fermat test for every coprime base
- Run Miller–Rabin by hand: write n − 1 = 2^s·d, square from a^d, and recognise a non-trivial square root of 1
- Implement a deterministic 64-bit test with 128-bit mulmod, the small-prime filter and the skip rule for bases that are multiples of n