The AKS Primality Test

I've had the privilege of being taught an introductory algorithms course, and later a course on cryptology, by Dr. Agrawal. He's a great person to talk to and to reason out problems with.