- News Home
12 December 2013 1:00 pm ,
Vol. 342 ,
The iconic 125-year-old Lick Observatory on Mount Hamilton near San Jose, California, is facing the threat of closure...
Recent results from the Curiosity Mars rover have helped scientists formulate a plan for the next phase of its mission...
A new, remarkably powerful drug that cripples the hepatitis C virus (HCV) came to market last week, but it sells for $...
In pretoothbrush populations, gumlines would often be marred by a thick, visible crust of calcium phosphate, food...
Evolutionary biologists have long studied how the Mexican tetra, a drab fish that lives in rivers and creeks but has...
Victorian astronomers spent countless hours laboriously charting the positions of stars in the sky. Such sky mapping,...
In an ambitious project to study 1000 years of sickness and health, researchers are excavating the graveyard of the now...
Stefan Behnisch has won awards for designing science labs and other buildings that are smart, sustainable, and...
- 12 December 2013 1:00 pm , Vol. 342 , #6164
- About Us
Acid Test for Primes
15 August 2002 (All day)
Quick: Is 341 a prime number? That's easy, if you know a few tricks. How about 4,294,967,297? Still a snap, if you use a computer. But what if the number has thousands of digits? Then things get murky, because the obvious way to settle the issue--systematically checking whether smaller numbers divide it--takes far too long. In recent decades, theorists have devised clever algorithms for telling whether a large number is 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 a provably efficient algorithm for testing primes (whole numbers evenly divisible only be themselves and 1). Manindra Agrawal, a professor of computer science, and two students, Neeraj Kayal and Nitin Saxena, announced their result early this month, e-mailing copies of it to a number of experts in computational number theory.
What especially intrigues number theorists is that the algorithm and the proof of its efficiency are both very simple. Like other modern tests for primes, the new algorithm is based on a fact that Pierre de Fermat (of Last Theorem fame) discovered in the 17th century: If n is prime, then it evenly divides an - a for any number a. Fermat's test makes it possible to prove that a number n is not prime without finding any of its factors. For example, 29 - 2 = 510, which is not divisible evenly by 9. Hence, 9 cannot be a prime number.
Unfortunately, some nonprime numbers also pass the test. To eliminate such "false positive" readings, the new algorithm runs a more elaborate but still elementary test, based on searching for pairs of numbers that fulfill a few simple conditions. If the search comes up dry, n is prime. The key to the algorithm's efficiency is that the search can be restricted to a small range of numbers.
It's a "delightful surprise" that such an easy algorithm had been missed all these years, says Carl Pomerance, a number theorist at Lucent Technologies' Bell Labs in Murray Hill, New Jersey. But cryptographers might have more mixed feelings. They rely on difficult computations, such as factoring large numbers, to safeguard computer systems. If primality can be vanquished so easily, who's to say that a quick algorithm for factoring isn't just around the corner? Or, as Pomerance puts it, "What else have we overlooked?"