Simple Recipe Creates Acid Test for Primes
Barry A. Cipra · Science · 2002
Quick, now: Is 341 a prime number? That one's pretty easy to answer. How about 4,294,967,297? That's still a snap if you use a computer. But what if the number you're interested in 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.