[Mac_crypto] NYT: New Method Said to Solve Key Problem in Math

[Mark Talbot]

h=
ttp://www.nytimes.com/2002/08/08/science/08MATH.html?pagewanted=3Dprint&po=
sition=3D
top

New Method Said to Solve Key Problem in Math
By SARA ROBINSON

Three Indian computer scientists have solved a longstanding mathematics=20=

problem by devising a way for a computer to tell quickly and=20
definitively whether a number is prime =97 that is, whether it is evenly=20=

divisible only by itself and 1.

Prime numbers play a crucial role in cryptography, so devising fast ways=20=

to identify them is important. Current computer recipes, or algorithms,=20=

are fast, but have a small chance of giving either a wrong answer or no=20=

answer at all.

The new algorithm =97 by Manindra Agrawal, Neeraj Kayal and Nitin Saxena=20=

of the Indian Institute of Technology in Kanpur =97 guarantees a correct=20=

and timely answer. Though their paper has not been published yet, they=20=

have distributed it to leading mathematicians, who expressed excitement=20=

at the finding.

"This was one of the big unsolved problems in theoretical computer=20
science and computational number theory," said Shafi Goldwasser, a=20
professor of computer science at the Massachusetts Institute of=20
Technology and the Weizmann Institute of Science in Israel. "It's the=20
best result I've heard in over 10 years."

The new algorithm has no immediate applications, since existing ones are=20=

faster and their error probability can be made so small that it is=20
practically zero. Still, for mathematicians and computer scientists, the=20=

new algorithm represents a great achievement because, they said, it=20
simply and elegantly solves a problem that has challenged many of the=20
best minds in the field for decades.

Asked why he had the courage to work on a problem that had stymied so=20
many, Dr. Agrawal replied in an e-mail message: "Ours was a completely=20=

new and unexplored approach. Consequently, it gave us hope that we might=20=

succeed."

The paper is now posted on the computer science department Web page at=20=

the Indian Institute of Technology (www.cse.iitk.ac.in).

Methods of determining whether a number is prime have captivated=20
mathematicians since ancient times because understanding prime numbers=20=

is the key to solving many important mathematical problems. More=20
recently, attention has focused on tests that run efficiently on a=20
computer, because such tests are part of the underlying mathematics of=20=

several widely used systems for encrypting data on computers.

So-called primality testing plays a crucial role in the widely used RSA=20=

algorithm, whose security relies on the difficulty of finding a number's=20=

prime factors. RSA is used to secure transactions over the Internet.


On Sunday, the researchers e-mailed a draft of the paper on the result=20=

to dozens of expert mathematicians and computer scientists. Dr. Carl=20
Pomerance, a mathematician at Bell Labs, said he received the paper on=20=

Monday morning and determined it was correct.

After discussing the draft with colleagues over lunch, Dr. Pomerance=20
arranged an impromptu seminar on the result that afternoon.

That he could prepare and give a seminar on the paper so quickly was "a=20=

measure of how wonderfully elegant this algorithm is," Dr. Pomerance=20
said. "This algorithm is beautiful."