News of the WeekNUMBER THEORY

Simple Recipe Creates Acid Test for Primes

See allHide 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

Log in to view the full text

Log in through your institution

Log in through your institution


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.