The research work called Primes is in P covering all of nine pages, its simplicity and its implications have made academia and industry scratch their heads and wonder why they did not think of it before.
Dr Agrawal, along with his students Neeraj Kayal and Nitin Saxena, achieved the breakthrough in solving the problem of testing for primality something that could impact Internet security and cryptography. While the two students have been in the limelight, the soft-spoken and modest Dr Agrawal has been content to merge into the background. But no more. The invitations have started pouring in. Come June, Dr Agrawal will be off to the Institute for Advanced Studies at Princeton, New Jersey on a years sabbatical. Princeton, because there are many number theorists there with whom he needs to talk so that he can solve the problem further, says Dr Agrawal. Honours too are finding their way including one for mathematical research from the Clay Mathematics Institute.
One of the fundamental problems that has dumfounded mathematicians is how to determine whether a given number is a prime number. Work has been going on to find an efficient algorithm for testing primality.
If the number happens to be a 150-digit number or a 300-digit number, the complexity is mind-boggling. Large prime numbers are fundamental for net encryption.
The AKS algorithm as it is now called, is the first unconditional, deterministic, time algorithm for testing whether a number is prime or not. If pursued further, this approach could also help in cracking a similar problem in factoring numbers.
Current Internet security is based on the fact that we cannot factor easily. The world record is at factoring a 155-digit number using one year of distributed work, says Dr Agrawal. He admits his algorithm is not practical and that it is fast but not fast enough. But he hopes that in a year or two, a much faster way of solving the problem will be found and this would be useful in cryptography. Dr Agrawal shows no eagerness to patent his solution solving the problem being his prime concern.
Tata Consultancy Services honoured this computer scientist at Pune on Tuesday where he made a presentation at the Tata Research Development and Design Centre.