|
A
Beautiful Mind From India Is Putting the Internet on Alert
By Lee Gomes
Copyright
© Dow Jones & Company
Inc. All Rights Reserved
Excerpts from article ...
full text available from the Wall Street Journal on the newsstand.
Send comments to
lee.gomes[!]wsj.com
http://online.wsj.com/article/0,,SB1036367360105172588,00.html?mod=technology%5Fcolumns%5Ffeatured%5Flsc
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 mathematicians for millennia: 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."
...
...
...
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.
|
|