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.
Download full paper ( PDF , Postscript )
Revised paper version ( PDF , Postscript )
Related Links:
Media Reports:
 |
Manindra Agrawal completed his BTech in 1986 and PhD in
1991, both from the Department of Computer Science & Engineering, IIT
Kanpur. He was then a Fellow at Chennai Mathematical Institute till 1995,
and Humboldt Fellow at University of Ulm during 1995-96. Since August
1996, he is at Department of Computer Science & Engineering, IIT
Kanpur.
Neeraj Kayal and Nitin Saxena both completed their BTech from the Department of Computer Science & Engineering, IIT Kanpur in May 2002. Currently, they are PhD students in the department. |
| From left to right: Nitin, Neeraj, and Manindra |
