A prime number is an integral number that cannot be divided by any integral number other than 1 and itself. For example, 2, 3, 5, 7, 11, 13, 17, 23, 97, 8191, are all prime numbers. These numbers are the building blocks of the number system, and scholars since ancient times have been engaged in studying their properties.
"There are infinitely many primes," says Agarwal, "and these occur in an apparently chaotic fashion on the number line."
But prime numbers play a crucial role in mathematics and computer science. "Indeed, a great deal of these areas result directly from studying the properties of prime numbers and their applications," he explains.
One of the fundamental problems, however, is to efficiently determine if a given number is a prime number.
"The usual method we learn in school," says Agarwal, "if used on large numbers (say with 100 digits) will take more time than the age of the universe, even if we use the fastest computers currently available."
"This problem," continues the professor, "known as the primality testing problem, is not only challenging mathematically, but also of great importance in practice because many modern cryptographic applications routinely require identification of primes with hundreds of digits."
Randomized (or coin-tossing) algorithms are used at present for primality testing. Though efficient, these algorithms have a small probability of giving the wrong answer.
It has, therefore, been a major challenge in computer science and mathematics to design an algorithm that is both efficient and always correct. Many approaches, including sophisticated techniques from mathematics, have been tried, but none had succeeded until now.
Agarwal and his team have been able to solve the problem in an innovative manner. An interesting aspect of their solution is that unlike many recent results in the area, the solution is short, elegant, and accessible even to undergraduate students.
They announced their result to the world scientific community on August 4, and it was immediately hailed as a very elegant solution to a challenging problem.
On August 7, they put their paper on the institute's Web site and within 24 hours more than 30,000 people downloaded the paper from all over the world. The world media has hailed their work as a major breakthrough, and scholars have called it the most important result of the decade in computer science.
Dr Carl Pomerance at Bell Labs told The New York Times that the algorithm is "wonderfully elegant". Professor R Balasubramanian, director of the Institute of Mathematical Sciences, Madras, says, "The algorithm will have far-reaching consequences".
The algorithm is available on the IIT Kanpur Web site at www.cse.iitk.ac.in/news/primality.pdf (You will need Acrobat Reader to view this link).