Edition: U.S. / Global

Outsider Math

Published: December 15, 2002

Prime numbers have baffled scientists for millennia. Primes do not occur in any easily discernible order -- which makes it very difficult to figure out whether a really huge number is prime or not. (And by ''really huge,'' we're talking thousands of digits long.) Ever since the time of the ancient Greeks, finding a simple way to prove a number is prime has been the holy grail of mathematics, and the hunt has nearly driven several scientists mad. As the mathematician Karl Friedrich Gauss wrote in 1801, ''The dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.''

This year, it finally arrived. On Aug. 6, the Indian mathematician Manindra Agrawal distributed a nine-page paper that rocked the scientific world. He had hit upon an ingenious algorithm to prove whether a number is prime, no matter how enormous. Within weeks, stunned mathematicians had kicked the tires and pronounced it sound. Security experts were just as shocked. Encryption programs used by banks and governments rely on increasingly large primes -- up to 300 digits, these days -- to keep criminals and terrorists at bay. This new algorithm could guarantee primes so massive they would afford almost perfect online security.

But most astonishing of all was the simplicity of the algorithm. You can scrawl it on a single sheet of paper -- double-spaced. It had been staring everyone in the face for years, like the Purloined Letter of mathematics. ''When you read the paper, you slapped yourself on the forehead and asked, Why didn't I think of this?'' says Carl Pomerance, a mathematician at Bell Labs.

Here's why. Math, like every other science, has become increasingly specialized. Prime-number theorists had been hacking away with number theory so complex and weird that barely 100 people worldwide could understand their calculations. But the new proof from India was created by a professor who isn't known as a number theorist -- and his two co-authors were still undergraduates. What's more, they employed a branch of math with which any high-school student would be familiar: polynomials, like the simple expression (A+B)². ''It's not really difficult at all,'' Agrawal says. ''When you show it, it's like, Is that it ?''

It is a fresh reminder of why history is riddled with innovations that came out of left field, delivered by amateurs toiling in their basements. Primes don't occur in any pattern -- and sometimes, neither do discoveries.