Primes are in P-time

On August 6, 2002, Agrawal, Kayal and Saxena announced a breakthrough: a deterministic polynomial-time algorithm recognizing prime numbers (AKS algorithm). This is one of the most important results in CS theory in the last few decades.

• The place to begin.
• Original paper (pdf | ps) by Agrawal, Kayal and Saxena.
• Slides ( pdf | ps | pdf four-up | ps four-up) from the presentation of the algorithm,
  prepared jointly with Mitsunori Ogihara from the University of Rochester.

back to spr's main page

December 13, 2002