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 n is a prime number, and a is a number co-prime to n (say n-1), then for any integer x, we have x^n+a\equiv (x+a)^n \pmod {n}. 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 {n\choose k}\equiv 0 \pmod {n} is if and only if n is prime? Hint: For proving that this is not true for non-prime n, consider {n\choose j}, where j is the smallest prime factor of n.

 

Published by ayushkhaitan3437

Hello! My name is Ayush Khaitan, and I'm a graduate student in Mathematics. I am always excited about talking to people about their research. Please please set up a meeting with me if you feel that I might have an interesting perspective to offer- https://calendly.com/ayushkhaitan/meeting-with-ayush

2 thoughts on “

  1. “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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: