200281521.jpg

Prime suspect. A surprising new algorithm serves as a quick lie detector for the positive integers.

Acid Test for Primes

By:
Barry Cipra
2002-08-15 (All day)
Posted In:

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?"

Posted In:

Related Stories

• Looking for new dollars, a nutritionist turns to crowd funding, and hopes she can raise what she needs by the deadline.

• Bias persists even in the face of contradictory facts

• The roots of cooperation may lie in antisocial behavior

• Mathematical formula shows best way to prevent ancient scrolls from deforming

• Someday a quantum computer may unlock all our secrets—if it isn't first stymied by simpler technologies.

• Simulations suggest it's disadvantageous for parasites to make their hosts mate more

• Decline of social networking site just years away, according to mathematical model

• Physicists debunk explanation for counterintuitive display

What's New

• A new find from NASA's Kepler orbiting observatory is the first Earth-sized planet to be detected in the habitable zone of a star

• First known sex organ reversal challenges theory of sexual selection

• Neurologists find mental crossroads for spatial hallucinations while treating a seizure patient

• New material marks a milestone in researchers' quest for energy efficiency

• Fossils of their ancient kin reveal dramatic changes over time

• Study argues that the evolutionary advantage of facial hair is disappearing

• Smithsonian gets one of the most complete skeletons ever found

• But move could be a legal tactic