Determining Whether Given Large Numbers Are Primes I

In 1801, C. Gauss wrote: “The problem of distinguishing prime numbers from composite numbers, and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic.

This is even more true today, Your use of ATM card or purchase something with credit card over the Web depends on the intractability of these problems.

In a successful Undergraduate Research Project (2002), Agrawal, Kayal and Saxena from India, discovered an amazing algorithm which can recognize primes deterministically in polynomial time of the inputs. This was a great breakthrough over the two centuries. AKS thereby won Clay Research Award 2002, the ICTP Prize 2003, the 2006 Gödel Prize and the 2006 Fulkerson Prize for this work.

In these two talks, we will explain the proof of this beautiful AKS algorithm. This proof can be understood well by undergraduates. We will also relate the concepts such as: complexity estimates, P versus NP, and the distinction between certifying primes and factorization of integers.