Just a small update: I came to the PSU Hackathon to learn the rudiments of coding. While random scrolling down wikipedia articles, I came across the AKS Primality test, created by three computer scientists at the Indian Institute of Technology, Kanpur. The Wikipedia page does a great job of explaining the algorithm. It is the first polynomial time algorithm ever to determine the primality of a number. And it is so simple!

The algorithm depends not the following fundamental fact: if is a prime number, and is a number co-prime to (say ), then for any integer , we have . This is a **necessary** and **sufficient** condition for primality! This is the simplest and most awesome thing I’ve seen in the recent past.

Note: Do you see why is if and only if is prime? Hint: For proving that this is not true for non-prime , consider , where is the smallest prime factor of .

“It is the first polynomial time algorithm […]” only with important qualifiers that only matter for theoretical purposes. The paper is great and it’s important, but the algorithm itself is not used as even the most recent improvements are massively slower than the proof methods we were using in the mid 1990s.

The fundamental fact you note is cool, but was known to Leibniz. The cool part is that it took 300+ years to rigorously modify that exponential method into a polynomial time method. As noted, the actual AKS algorithm is a bit more complicated than that lemma.

Thanks for your comment! I didn’t know that