[crypto] [observer@westnet.com: New Method Said to Solve Key Problem in Math]

R. Hirschfeld ray@unipay.nl
Sat, 10 Aug 2002 11:24:53 +0200


------- Start of forwarded message -------
Date: Sat, 10 Aug 2002 00:00:39 -0400 (EDT)
From: "John F. McMullen" <observer@westnet.com>
X-X-Sender: observer@westnet
To: Cryptography Mailing List <cryptography@wasabisystems.com>
Subject: New Method Said to Solve Key Problem in Math 
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: owner-cryptography@wasabisystems.com
Precedence: bulk
Content-Length: 4583

>From the New York Times --
http://www.nytimes.com/2002/08/08/science/08MATH.html

New Method Said to Solve Key Problem in Math
by Sara Robinson

Three Indian computer scientists have solved a longstanding mathematics
problem by devising a way for a computer to tell quickly and definitively
whether a number is prime  that is, whether it is evenly divisible only by
itself and 1.

Prime numbers play a crucial role in cryptography, so devising fast ways
to identify them is important. Current computer recipes, or algorithms,
are fast, but have a small chance of giving either a wrong answer or no
answer at all.

The new algorithm  by Manindra Agrawal, Neeraj Kayal and Nitin Saxena of
the Indian Institute of Technology in Kanpur  guarantees a correct and
timely answer. Though their paper has not been published yet, they have
distributed it to leading mathematicians, who expressed excitement at the
finding.

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

The new algorithm has no immediate applications, since existing ones are
faster and their error probability can be made so small that it is
practically zero. Still, for mathematicians and computer scientists, the
new algorithm represents a great achievement because, they said, it simply
and elegantly solves a problem that has challenged many of the best minds
in the field for decades.

Asked why he had the courage to work on a problem that had stymied so
many, Dr. Agrawal replied in an e-mail message: "Ours was a completely new
and unexplored approach. Consequently, it gave us hope that we might
succeed."

The paper is now posted on the computer science department Web page at the
Indian Institute of Technology (www.cse.iitk.ac.in).

Methods of determining whether a number is prime have captivated
mathematicians since ancient times because understanding prime numbers is
the key to solving many important mathematical problems. More recently,
attention has focused on tests that run efficiently on a computer, because
such tests are part of the underlying mathematics of several widely used
systems for encrypting data on computers.

So-called primality testing plays a crucial role in the widely used RSA
algorithm, whose security relies on the difficulty of finding a number's
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 to
dozens of expert mathematicians and computer scientists. Dr. Carl
Pomerance, a mathematician at Bell Labs, said he received the paper on
Monday morning and determined it was correct.

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

That he could prepare and give a seminar on the paper so quickly was "a
measure of how wonderfully elegant this algorithm is," Dr. Pomerance said.
"This algorithm is beautiful."

Copyright 2002 The New York Times Company

*** FAIR USE NOTICE. This message contains copyrighted material whose use
has not been specifically authorized by the copyright owner. The
'johnmacsgroup' Internet discussion group  is is making it available
without profit to group members who have expressed a prior interest in
receiving the included information in their efforts to advance the
understanding of literary, educational, political, and economic issues,
for non-profit research and educational purposes only. I believe that this
constitutes a 'fair use' of the copyrighted material as provided for in
section 107 of the U.S. Copyright Law. If you wish to use this copyrighted
material for purposes of your own that go beyond 'fair use,' you must
obtain permission from the copyright owner.

For more information go to:
http://www.law.cornell.edu/uscode/17/107.shtml


   "When you come to the fork in the road, take it" - L.P. Berra
   "Always make new mistakes" -- Esther Dyson
   "Be precise in the use of words and expect precision from others" -
    Pierre Abelard
                          John F. McMullen
   johnmac@acm.org ICQ: 4368412 Fax: (603) 288-8440 johnmac@cyberspace.org
                  http://www.westnet.com/~observer



- ---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
------- End of forwarded message -------