This is BrainLog, a blog by Dan Sanderson. Older entries, from October 1999 through September 2010, are preserved for posterity, but are no longer maintained. See the front page and newer entries.

November 11, 2002

PRIMES is in P.

Prof. Manindra Agarwal and two of his students, Nitin Saxena and Neeraj Kayal (both BTech from CSE/IITK who have just joined as Ph.D. students), have discovered a polynomial time deterministic algorithm to test if an input number is prime or not. Lots of people over (literally!) centuries have been looking for a polynomial time test for primality, and this result is a major breakthrough, likened by some to the P-time solution to Linear Programming announced in the 70s.

One of the main features of this result is that the proof is neither too complex nor too long (their preprint paper is only 9 pages long!), and relies on very innovative and insightful use of results from number theory.

See also their FAQ, which reviews related concepts.