Testing for Primality

Testing for Primality

1. Problem (beginner)

RSA needs 300-digit primes — can't trial-divide (too slow!). Need FAST tests: probabilistic (Miller-Rabin: quick, tiny error!) + deterministic check for small $n$.

2. Test Ladder (exam order!)

Test	Idea	Verdict
Trial division (to $\sqrt{n}$)	divide by 2,3,5...	exact, SLOW (small $n$ only!)
Fermat ($a^{n-1}$ mod $n = 1$?)	fail → composite!	fast, fooled by Carmichael!
Miller-Rabin (witness loop!)	write $n-1 = 2^{k} \times m$, square-check!	BEST (used in practice!)

3. Miller-Rabin Sketch (exam steps!)

input odd n, rounds t (more rounds = safer!)
write n-1 = 2^k × m (m odd!)
pick random a; compute b = a^m mod n
if b = 1 or ±1 chain hits n-1 → PROBABLY prime (pass!)
else → COMPOSITE (witness found!)
repeat t times (error ≤ (1/4)^t — t=10 → one in a million!)

Example: $n = 561$ (Carmichael!) passes Fermat base 2, but Miller-Rabin base 2 exposes it → COMPOSITE!

4. Practice Recipe (real RSA!)

Trial-divide small primes → Fermat quick-filter → Miller-Rabin $t = 10$-$20$ → accept! Generate random odd 300-digit + test till pass!

5. Exam Points

• Three tests + Carmichael trap — 5-7 marks, very frequent.
• Miller-Rabin steps + error $(1/4)^{t}$ — 5 marks, favourite.
• Trial limit $\sqrt{n}$ — 2 marks, frequent.