Puzzling Adventures: Prime Spies; October 2002; Scientific American Magazine; by Dennis E. Shasha; 1 Page(s)

Number theory, once thought an esoteric discipline concerned with curious properties of prime numbers, turns out to form the underpinnings of modern cryptography. The Rivest-Shamir-Adleman public-key cryptography algorithm (RSA, for short) used in most e-commerce transactions relies on the (unproved but widely believed) difficulty of factoring a number that is the product of two primes.

Multiplying two large primes is an example of a so-called one-way function: the multiplication takes only a few microseconds, and the time is proportional to the length of the binary representations of the numbers; in contrast, discovering the two primes given the product is slow, taking hours for a 512-bit product and continuing a slow exponential climb (in the length of the product) after that. For 2,048-bit numbers, factoring is considered impractical, as far as is publicly known. Fast factoring algorithms, if they exist, would have untold applications for industrial and even military espionage.