- News Home
6 March 2014 1:04 pm ,
Vol. 343 ,
Magdalena Koziol, a former postdoc at Yale University, was the victim of scientific sabotage. Now, she is suing the...
Antiretroviral drugs can protect people from becoming infected by HIV. But so-called pre-exposure prophylaxis, or PrEP...
Two studies show that eating a diet low in protein and high in carbohydrates is linked to a longer, healthier life, and...
Considered an icon of conservation science, researchers at World Wildlife Fund (WWF) headquarters in Washington, D.C.,...
The new atlas, which shows the distribution of important trace metals and other substances, is the first product of...
Early in April, the first of a fleet of environmental monitoring satellites will lift off from Europe's spaceport in...
Since 2000, U.S. government health research agencies have spent almost $1 billion on an effort to churn out thousands...
- 6 March 2014 1:04 pm , Vol. 343 , #6175
- 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?"