In August 2002, three mathematicians at IIT Kanpur — a professor and two students who had just finished their B.Tech — posted an eight-page paper titled "PRIMES is in P." It contained the first deterministic, unconditional, polynomial-time primality test in history. A 30-year-old open problem in computer science was over.
The whole algorithm comes from a single polynomial identity, sitting just above Fermat's little theorem in a place nobody had thought to look:
(x + a)^n ≡ x^n + a (mod x^r − 1, n)
This video unpacks how the AKS algorithm works — from trial division and Carmichael numbers, through Miller–Rabin's probabilistic era, to the polynomial identity at the heart of AKS, and finally the group-theoretic argument that makes the whole proof fit on three pages.
Chapters
00:00 The ancient question
02:00 The probabilistic era
04:14 August 2002, IIT Kanpur
06:00 Fermat's polynomial identity
08:08 Truncate mod x^r − 1
10:27 Choosing the right r
12:24 The heart of the proof
14:53 Polynomial forever
References
- Agrawal, Kayal, Saxena (2002), "PRIMES is in P," Annals of Mathematics
- Lenstra & Pomerance (2005), tighter analysis: Õ(log⁶ n)
- Granville (2004), "It is easy to determine whether a given integer is prime"
#math #primes #algorithm #computerscience #manim #numbertheory
