From: Brett Paatsch (paatschb@ocean.com.au)
Date: Fri Aug 30 2002 - 18:29:50 MDT
Hi All,
Have been a bit busy to read recent posts but a quick scan of subject
heading suggest this article "Simple Recipe Creates Acid Test for Primes"
(Science: Vol 297. 16 Aug 2002, p1105) may not yet have been picked up.
(If it has my apologies for reposting).
Others on this list will have a better understanding of this area than I but
I understand that Public Key Infrastructure and most current forms of
encryption underpinning the global financial system and the privacy of point
to point electronic communications generally depends on the simple
mathematical phenomena that very large prime numbers take too long to factor
via sequential computer searches and no non-sequential algorithms had been
found. To the extent this is true and the developments in refereed to in the
article referenced are real, the ramifications for the global financial
systems, privacy and open society would and should be of interest to more
than number theory aficionados.
The article in Science states:
"In recent decades, (number) theorists have devised clever algorithms for
telling whether a large number is a prime, but none that could be proven to
work quickly.
Until now.
Three computer scientists at the Indian Institute of Technology in Kanpur
have found what researchers have long sought: a provably efficient algorithm
for testing primes... Manindra Agrawal, a professor of computer science, and
two students, Neeraj Kayal and Nitin Saxena, announced their results early
this month, e-mailing copies of it to a number of experts in computational
number theory.
(Hendrik Lenstra at University of Berkeley says) "the new results tidies up
one of the corners of modern cryptography, which relies on hard-to factor
composite (non-prime) numbers to encrypt information. Although the algorithm
is not practical at present, just knowing that it exists "simplifies our
picture of what is going on," notes Andrew Odlyzko, a computational number
theorist and director of the Digital Technology Centre at the University of
Minnesota, Twin Cities."
"It's a bit of a surprise that such an easy algorithm had been missed all
these years," say Carl Pomerance, a number theorist at Bell Labs in Murray
Hill, New Jersey. "It's a delightful surprise - and perhaps a bit of an
embarrassment for those who have been working in the field, such as myself".
"Cryptographers might have more mixed feelings. They rely on now-difficult
number theoretic computations, such as factoring large numbers, to safeguard
cryptosystems that have become the mainstays of the computer security
business. If primality can be vanquished so easily, who's to say that a
polynomial-time algorithm for factoring isn't just around a corner?"
Brett
.
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:16:34 MST