| Speaker: |
Richard Dore Undergraduate Student Department of Mathematical Sciences Carnegie Mellon University |
|
| Title: |
The polynomial time test for primality of Agrawal, Kayal and Saxena
|
|
| Abstract: |
The concept of primality has been an interest of mathematics dating back to ancient times. The ability to test primality efficiently is both theoretically interesting and of practical importance. In other words, is there some algorithm that tests primality in time polynomial in the size of it's input? In 1976, Gary Miller gave an algorithm that works in polynomial time assuming the Extended Reimann Hypothesis. Various results of the 80s and early 90s revealed that primality testing is in all the standard randomized polytime complexity classes. An algorithm that runs in time log(n)^O(log log log n) is also known.
Despite all this, no deterministic, nonrandom algorithm was known. Then, earlier this year, Manindra Agrawal of IIT Kanpur and two of his PhD student, Neeraj Kayal and Nitin Saxena, came up with an algorithm that runs in O(log(n)^12), and under a widely held belief about the distribution of the Sophie Germain primes, turns out to be O(log(n)^6). The algorithm is reasonably simple. The efficiency of the algorithm is easy; the most difficult part is the proof of correctness for composite inputs.
In this talk, I will present some background, and give the algorithm and the proofs of correctness and efficiency. For those interested, the original paper can be found at http://www.cse.iitk.ac.in/news/primality.html.