 News Home
 Hot Topics
Current
 Categories
 From the Magazine

17 April 2014 12:48 pm ,
Vol. 344 ,
#6181

Officials last week revealed that the U.S. contribution to ITER could cost $3.9 billion by 2034—roughly four times the...

An experimental hepatitis B drug that looked safe in animal trials tragically killed five of 15 patients in 1993. Now,...

Using the two highquality genomes that exist for Neandertals and Denisovans, researchers find clues to gene activity...

A new report from the Intergovernmental Panel on Climate Change (IPCC) concludes that humanity has done little to slow...

Astronomers have discovered an Earthsized planet in the habitable zone of a red dwarf—a star cooler than the sun—500...

Three years ago, Jennifer Francis of Rutgers University proposed that a warming Arctic was altering the behavior of the...


17 April 2014 12:48 pm ,
Vol. 344 ,
#6181
 ScienceNow
 ScienceInsider
 ScienceLive
 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 issuesystematically checking whether smaller numbers divide ittakes 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, emailing 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 a^{n}  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, 2^{9}  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?"
Related sites
Manindra Agrawal's site, with a link to the paper
The Prime pages
Posted In: