[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [sc-users] [OT] prime numbers
They provided a new algorithm to test if a number is prime, not a new
algorithm to factor a number. The latter is required to break
encryption. So far they have made encrypting more secure, not less, by
being able to be absolutely certain that the keys used are prime
instead of being only 99.999% certain as with the probablistic tests
used previously.
On Monday, December 30, 2002, at 07:18 PM, christian.hresko wrote:
pretty cool stuff:
The e-mail that three Indian computer scientists sent to a few dozen
of the world's best mathematicians on August 4 was shockingly simple
and elegant. Their algorithm, a scant 13 lines long, provided a test
for whether a number is prime. That may seem like a forbidding
intellectual curiosity, but large prime numbers have become a major
factor in encryption technologies, especially those that govern
financial transactions over the Internet. Although mathematicians have
known for more than 2,000 years that there are an infinite number of
primes—integers such as 7 and 43 divisible only by 1 and
themselves—testing larger numbers to determine if they are prime has
proved surprisingly difficult and time-consuming. After a number gets
to be more than 10,000 digits long, even powerful computers quickly
become bogged down in the task, forcing scientists to rely on
less-than-perfect probability techniques.
So when mathematicians around the world opened their e-mail the
next morning and looked at the work of Manindra Agrawal, Neeraj Kayal,
and Nitin Saxena of the Indian Institute of Technology in Kanpur, the
world changed. New knowledge, especially in mathematics, is often
disruptive. The algorithm points toward an efficient solution to an
old problem but suggests a new one as well. Encryption protocols used
over the Internet rely on the difficulty of factoring into primes.
Once that becomes easy, those protocols may be rendered useless.
Despite this potential turmoil, mathematics is a field in which
simplicity and beauty are standards of excellence, and this proof
passes those tests.
wasn't this thought to be NP-Hard?
christian
--
--- james mccartney james@xxxxxxxxxxxxxx <http://www.audiosynth.com>
SuperCollider - a real time synthesis programming language for the
PowerMac.
<ftp://www.audiosynth.com/pub/updates/SC2.2.16.sea.hqx>