Math Discovery Rattles Net Security

Will Manindra Agrawal bring about the end of the Internet as we know it?  The question is not as ridiculous as it was just two months ago.  Dr. Agrawal is a 36-year old theoretical computer scientist at the Indian Institute of Technology in Kanpur, India.  In August, he solved a problem that had eluded millennia of mathematicians: developing a method to determine with complete certainty if a number is prime.

Prime numbers are those divisible only by themselves and 1.  While small primes like 5 or 17 are easy to spot, for very large numbers hundreds of digits long, there has never been a formula of “primality testing” that didn’t have a slight chance of error.  Besides being a show-stopping bit of mathematics, the work was big news for the Internet.  Very large prime numbers are the bedrock of Internet encryption, the sort a browser uses when people shop online.

The present encryption system takes two big and secret prime numbers and multiplies them.  For a bad guy to decrypt your message, he’d need to take the product of that multiplication and figure out the two prime numbers used to generate it.  It’s called the “factoring problem,” and fortunately it’s something no one on Earth knows how to do quickly.  A speedy method of factoring would make existing Internet security useless, not a pleasant thought in this Internet age.

Dr. Agrawal's work involved only testing whether a number is prime, not the factoring problem.  However, there are enough connections and similarities between the two that mathematicians and computer scientists from all over the world flew in to hear Dr. Agrawal on whirlwind tour last week through M.I.T., Harvard and Princeton.  At Princeton, Dr. Agrawal's lecture was the sort of deep math that only the most beautiful minds could understand.  In a subsequent and more people-friendly interview, he said he started his work three years ago.  He was dealing with a different problem, called identify testing, when he noticed the solution hinted at a potential fresh assault on prime-number testing.

It was a long three years. While no slouch in math, Dr. Agrawal said he sometimes had to use Google to find information on the more recondite aspects of number theory.  His "Eureka!" moment came when he was driving his daughter to school and particularly complicated mathematical set suddenly fell into place. 

The computer scientists who heard Dr. Agrawal speak said, with considerable pride, that he was obviously one of them, because of the way he proceeded purposely — “algorithmically” is the word they used — toward his goal. (As computer scientists tell it, mathematicians tend to be too showy and discursive about things.)  Dr. Agrawal is the first to admit that his work, for all its elegant math, has no immediate practical application.  He says the current tests for prime numbers, even with their slight chance of error, are good enough for most people, as well as extremely fast.

Will he now move on to the factoring challenge?  Yes, in due time.  The best current method of factoring, he explains, is the "Number Field Sieve."  "Best" is a relative term, since all computers in the world would still need untold trillions of years to use the system to factor just one big number.  Dr. Agrawal states "Factoring is a natural problem, and natural problems should have a natural complexity to them.  However, the Number Field Sieve is not a natural complexity.  It looks strange.  There must be something more natural than this out there.

What he doesn’t yet know, however, is whether a more “natural” approach to factoring also would be appreciably faster than current methods.  Which is of course, the $64 billion question.  Most mathematicians say they don’t lose any sleep about waking up and finding the factoring problem solved.  It’s just too hard, they say.  Hence, this difficulty was the very reason the method was chosen for Internet security in the first place.

However, others, like Princeton math professor Peter Sarnak who hosted Dr. Agrawal on campus, aren’t so convinced of the factoring problem’s eternal intractability.  "The fact that one venerable mathematics problem has just been solved," said Dr. Sarnak, "might inspire new assaults on factoring, possibly even using some of Prof. Agrawal’s techniques."  Dr. Agrawal says factoring will have to wait a few years; he wants to warm up with something easier, like “derandomizing polynomial time algorithms,” for instance.  The professor worked on primality testing with two of his graduate students: Neeraj Kayal and Nitin Saxena.  They had planned to join him on his U.S. victory tour, but the American Embassy in New Delhi, the times being what they are, refused them visas.  The two young geniuses had to stay home.