** The Wall Street Journal Monday, November 4, 2002
BOOMTOWN By LEE GOMES
A Beautiful Mind From India Is Putting the Internet on Alert
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.
Prof. 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, those hundreds of digits long, there
never had 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
your browser uses when you are shopping online.
That 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.
Prof. Agrawal's work involved only testing whether a number is prime, not the
factoring problem. Still, there are enough connections and similarities between
the two that mathematicians and computer scientists from all over the East
Coast flew in to hear Prof. Agrawal on a whirlwind tour last week through the likes
of M.I.T., Harvard and Princeton.
At Princeton, Prof. Agrawal's lecture was the sort of deep math that only the
most beautiful minds could understand. In a subsequent, and more lay-friendly, interview
he said he started his work three years ago. He was dealing with a different
problem, called identity 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, Prof. Agrawal said he
sometimes had to use Google to find information on the more recondite aspects
of number theory. His Eureka! moment came in July. As he was driving his
daughter to school on his motor scooter, a particularly complicated
mathematical set suddenly fell into place.
The computer scientists who heard Prof. 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.)
Prof. 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.
Still, 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 the
computers in the world would still need
untold trillions of years to use the system to factor just one big number.
Prof. Agrawal writes the Number Field Sieve equation on a piece of paper, looks
at it and winces. "Factoring is a natural problem. And natural problems should
have a natural complexity to them. But this,” he says, pointing to the
equation, "this is not natural complexity. This looks very 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.
And that, of course, is 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. (This difficulty was
the very reason the method was chosen for Internet security in the first
place.)
But others, like Princeton math professor Peter Sarnak who hosted Prof. Agrawal
on campus last week, aren't so convinced of the factoring problem's eternal intractability.
The fact that one venerable mathematics problem has just been solved, said
Prof. Sarnak, might inspire new assaults on factoring, possibly even using some
of Prof. Agrawal's techniques.
Prof. Agrawal said 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.
* Send comments to [email protected], and check back Friday for selected
letters at WSJ.com/BoomTown2.
ABOUT LEE GOMES
Lee Gomes, who writes the Boom Town column on Monday and the Boom Town
Exchange3 on Friday, has been covering various topics, technical and otherwise,
for The Wall Street Journal since 1996. He is a graduate of the University of
Hawaii and the Columbia University Graduate School of Journalism, and lives in San
Francisco.