Title:Primality Detection in Polynomial Time (after Agrawal,
Kayal, & Saxena)
Abstract:
On August 6, 2002, Manindra Agrawal, and two of his students (Neeraj Kayal
and Nitin Saxena), from the Computer Science department of the Indian
Institute of Technology (Kanpur) posted on a web-site a preprint proving
the following:
Theorem: Deciding whether a positive integer n is prime can be done within O(log^{12} n) bit operations, i.e., time polynomial in the number of digits. This was a major breakthrough as previous algorithms either (a) assumed unproven number theoretic conjectures like the Extended Riemann Hypothesis, (b) had a small but positive error probability, or (c) ran in time exponential in the number of digits. The algorithm indeed works as claimed, having been checked by many experts including Hendrik W. Lenstra, Jr. and Carl Pomerance. We give a simple description of the algorithm. This actually turns out to be easy since the algorithm itself is simple and elegant --- a wonderful surprise for a problem which has withstood attacks by number theorists since at very least the 19th century. Along the way, we give a little number theoretic background, as well as explanations of what the complexity classes P, ZPP, RP, BPP, and NP (not to mention coRP and coNP) are. Time permitting, we'll see what the ideas were behind the earlier, more complicated non-deterministic algorithms. |

Return to the seminar page.

Please send comments about this page to J. Maurice Rojas at rojas@math.tamu.edu.