News of the WeekNUMBER THEORY

Simple Recipe Creates Acid Test for Primes

+ See all authors and affiliations

Science  16 Aug 2002:
Vol. 297, Issue 5584, pp. 1105-1106
DOI: 10.1126/science.297.5584.1105b

You are currently viewing the summary.

View Full Text


Theorists have devised clever algorithms for telling whether a large number is prime, but none that could be proven to work quickly. Now three computer scientists in India have composed one that fills the bill. The new primality test runs in "polynomial time"--the gold standard of efficiency in computer science--and is so simple that other theorists wonder how they missed it.