We have completed maintenance on DiscoverMagazine.com and action may be required on your account. Learn More


Jan 1, 2003 6:00 AMNov 12, 2019 6:34 AM


Sign up for our email newsletter for the latest science news

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

1 free article left
Want More? Get unlimited access for as low as $1.99/month

Already a subscriber?

Register or Log In

1 free articleSubscribe
Discover Magazine Logo
Want more?

Keep reading for as low as $1.99!


Already a subscriber?

Register or Log In

More From Discover
Recommendations From Our Store
Shop Now
Stay Curious
Our List

Sign up for our weekly science updates.

To The Magazine

Save up to 40% off the cover price when you subscribe to Discover magazine.

Copyright © 2024 Kalmbach Media Co.