Prime efforts may boost encryption
Computer scientists in India crack an age-old math problem to help quickly prove whether a figure is a prime number--a vital step in computer cryptography.
RSA, a popular encryption algorithm used in securing Internet commerce, is built on the assumption that when prime numbers--those evenly divisible only by themselves and the number one--are large enough, they're nearly impossible to generate and determine.
Testing then confirms whether the initial numbers were in fact prime. The current algorithms used in so-called primality tests are speedy but have a miniscule probability of producing a wrong answer.
But a new algorithm, developed at the Indian Institute of Technology in Kanpur by Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena, is believed to generate correct results each and every time.
"The most glaring weakness in the current cryptographic software is that we can't prove with a guarantee that a number is prime," said Eric Allender, a professor of computer science at the State University of New Jersey at Rutgers. "This new algorithm answers a fundamental question that has been open for some centuries and studied intensely for several decades."
Although Agrawal's paper on the subject, titled "Primes is in P," has yet to be published, it is causing a stir in the field because of the way it handles a math problem that has captivated mathematicians as far back as the ancient Chinese and Greeks. Several leading computer scientists and mathematicians have studied the paper.
"Some of the preceding work was quite complex," Allender said. "This is really a lovely, crisp and elegant algorithm."
Practical uses for the algorithm, computer scientists admit, are still far off.
"Our algorithm is slower than the fastest-known primality testing algorithms," Agrawal said. "The satisfying part of our algorithm is that it is completely deterministic as opposed to earlier ones that may make an error--even though rarely."
Computers scientists said that in many areas, people are often willing to live with that small probability of error. But with the increasing reliance on encryption in fields such as banking and secure communications, a greater priority is being placed on strengthening cryptography.
"The greatest import of this (algorithm) is as a theoretical result and as a first step," Allender said. "It opens the door. There will be subsequent refinements and improvements in the techniques to make it more practical."