You are currently viewing the summary.
View Full TextLog in to view the full text
AAAS login provides access to Science for AAAS members, and access to other journals in the Science family to users who have purchased individual subscriptions.
More options
Download and print this article for your personal scholarly, research, and educational use.
Buy a single issue of Science for just $15 USD.
Summary
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.
