Wednesday, January 01, 2003

7. Test for Primes Menaces Internet

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. — David Appell

Comment on this article
Collapse bottom bar

Log in to your account

Email address:
Remember me
Forgot your password?
No problem. Click here to have it emailed to you.

Not registered yet?

Register now for FREE. It takes only a few seconds to complete. Register now »