One of the great virtues of the RSA technique is its adaptability. If you want more security, you can simply use larger primes p and q to create the public key n. Prime numbers are not only fairly common but there is a limitless supply of them; so you’ll never run out.

Indeed, key length is the parameter that governs the security of the RSA cryptosystem, and all similar mathematical systems. In 1977, when Rivest, Shamir, and Adleman announced their system, they posed a famous challenge in Scientific American, offering $100 to anyone who could decode a message that was encoded using a 129-digit key. (Their number was n = 114381625757-8888676692357799761466120102182967212423625625618429357069352-457338978305971235639587050-58989075147599290026879543541. Can you find its two prime factors?) With the factoring methods and computer technology then available, the three codemakers estimated that it would take someone 40 quadrillion years to break the cipher.

This was like waving a red flag in front of a bull. In the end it took only 17 years, accompanied by tremendous advances in computer technology and factoring algorithms, for persistent mathematicians and computer scientists to decode the message. Led by a group of experts, a team of more than 600 volunteers in two dozen countries, collaborating over the Internet, factored the RSA 129-digit key in 1994. The team used a new factoring algorithm called the “quadratic sieve,” invented in 1981 by Carl Pomerance, now at Bell Labs, which has the ability to distribute the computation among many computers.

Even though the message was decoded (it read: “The magic words are squeamish ossifrage.”), the three cryptologists had proved their larger point. Despite knowing exactly how RSA worked, the experts needed a huge investment of time, widespread use of the Internet, and the development of new mathematical methods to crack it. RSA-129 was broken, but RSA itself was still secure. RSA factoring challenges are still mounted periodically. For example, one of the RSA 155-digit keys was factored in 1999 using the “number field sieve” invented by John Pollard. This shows that users must use longer keys as technology improves—perhaps 300 digits instead of 129 or 155. There is only one development that would seriously threaten the security of RSA itself: a breakthrough in the time it takes to split a number into its prime factors.

At present, it is much easier to determine whether a number is prime than it is to find the divisors of a composite number. As noted above, Fermat’s little theorem can be used as a sort of litmus test for primality. If a number n fails the test—that is, if some smaller number a, when multiplied by itself n times and then reduced modulo n, does not yield the original number a back again—then you are guaranteed that n is composite. (Even though you have no clue what its divisors are!)

Unfortunately, this test is not quite so foolproof in the reverse direction. A few composite numbers n do manage to pass Fermat’s test for primality. (The smallest such “pseudoprime” is 561, which is 3 × 11 × 17.) In recent years, mathematicians have come closer and closer to eliminating this loophole. And in 2002 three computer scientists—two of them undergraduate students—finally finished the job. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of the Indian Institute of Technology in Kanpur, India, astounded the mathematical world when they discovered an improved version of Fermat’s test that has no exceptions. More than that, they demonstrated that their method could be programmed to run quickly on a computer. No previous primality test had met this double “gold standard” of guaranteed correctness and practicability.

Some of the initial publicity over this new primality test suggested that it might weaken the RSA cryptosystem. In fact, precisely the opposite is the case. The RSA system depends on the validity of two assertions: Finding prime numbers must be easy (otherwise Bob would never be able to generate his keys), but finding the prime divisors of composite numbers must be hard (otherwise Eve would be able to read Bob’s mail). Thanks to Agrawal, Kayal, and Saxena, the first of these two statements can now be made confidently, without any hemming and hawing about pseudoprimes. But their work has no effect on the second assertion. The only grounds for worry are psychological: If mathematicians missed the Agrawal et al. primality test for so long, perhaps they could also be missing an easy factorization method.