New Method Said to Solve Key Problem in Math
By SARA ROBINSON
"Three Indian computer scientists have solved a longstanding mathematics problem by devising a way for a computer to tell quickly and definitively whether a number is prime � that is, whether it is evenly divisible only by itself and 1."
"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. "