IITBHF and IITBAA (http://www.iitbombay.org)

Primes in P

Prof. Manindra Agarwal and two of his students, Nitin Saxena and Neeraj Kayal, both B.Tech. from IIT Kanpur 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 the 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. You can read the full paper in PDF format or in Postscript, and other news report include:

NOTE: Click here for a more recent article from the Science section of the New York Times.

The above development is being compared to another groundbreaking groundbreaking by yet another IITian, IIT Bombay alumnus Narendra Karmarkar, who invented a ground-breaking algorithm in the field of linear programming in 1984 ... more.

New Method Said to Solve Key Problem in Math (New York Times)

By SARA ROBINSON

© 2002 The New York Times Company
Excerpts from article ... full text available from the New York Times on the newsstand.

http://www.nytimes.com/2002/08/08/science/08MATH.html

August 8, 2002

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.

Prime numbers play a crucial role in cryptography, so devising fast ways to identify them is important. Current computer recipes, or algorithms, are fast, but have a small chance of giving either a wrong answer or no answer at all.

The new algorithm - by Manindra Agrawal, Neeraj Kayal and Nitin Saxena of the Indian Institute of Technology in Kanpur - guarantees a correct and timely answer. Though their paper has not been published yet, they have distributed it to leading mathematicians, who expressed excitement at the finding.

...

The new algorithm has no immediate applications, since existing ones are faster and their error probability can be made so small that it is practically zero. Still, for mathematicians and computer scientists, the new algorithm represents a great achievement because, they said, it simply and elegantly solves a problem that has challenged many of the best minds in the field for decades.

Asked why he had the courage to work on a problem that had stymied so many, Dr. Agrawal replied in an e-mail message: "Ours was a completely new and unexplored approach. Consequently, it gave us hope that we might succeed."

The paper is now posted on the computer science department Web page at the Indian Institute of Technology (http://www.cse.iitk.ac.in).

Methods of determining whether a number is prime have captivated mathematicians since ancient times because understanding prime numbers is the key to solving many important mathematical problems. More recently, attention has focused on tests that run efficiently on a computer, because such tests are part of the underlying mathematics of several widely used systems for encrypting data on computers.

So-called primality testing plays a crucial role in the widely used RSA algorithm, whose security relies on the difficulty of finding a number's prime factors. RSA is used to secure transactions over the Internet.

...

Please review the Terms of Usage provided on the disclaimer page prior to accessing this website.
ACCESSING THIS WEBSITE SIGNIFIES YOUR AGREEMENT TO THE TERMS OF USAGE.