When the RSA algorithm was first made public in 1977, Rivest, Shamir, and Adleman made the following challenge.

Let the RSA modulus be

and let $e=9007$ be the encryption exponent. The ciphertext is

Find the message.

The only known way of finding the plaintext is to factor $n$. In 1977, it was estimated that the then-current factorization methods would take $4\times {10}^{16}$ years to do this, so the authors felt safe in offering $100 to anyone who could decipher the message before April 1, 1982. However, techniques have improved, and in 1994, Atkins, Graff, Lenstra, and Leyland succeeded in factoring $n$.

They used 524339 “small” primes, namely those less than 16333610, plus they allowed factorizations to include up to two “large” primes between 16333610 and $2^{30}$. The idea of allowing large primes is the following: If one large prime $q$ appears in two different relations, these can be multiplied to produce a relation with $q$ squared. Multiplying by $q^{-2}(\text{mod}n)$ yields a relation involving only small primes. In the same way, if there are several relations, each with the same two large primes, a similar process yields a relation with only small primes. The “birthday paradox” (see Section 12.1) implies that there should be several cases where a large prime occurs in more than one relation.

Six hundred people, with a total of 1600 computers working in spare time, found congruence relations of the desired type. These were sent by e-mail to a central machine, which removed repetitions and stored the results in a large matrix. After seven months, they obtained a matrix with 524339 columns and 569466 rows. Fortunately, the matrix was sparse, in the sense that most of the entries of the matrix were 0s, so it could be stored efficiently. Gaussian elimination reduced the matrix to a nonsparse matrix with 188160 columns and 188614 rows. This took a little less than 12 hours. With another 45 hours of computation, they found 205 dependencies. The first three yielded the trivial factorization of $n$, but the fourth yielded the factors

Computing ${9007}^{-1}(\text{mod}(p-1)(q-1))$ gave the decryption exponent

Calculating $c^d(\text{mod}n)$ yielded the plaintext message

which, when changed back to letters using $a=01\text{,}b=02\text{,}\dots \text{,}\text{blank}=00$, yielded

(a squeamish ossifrage is an overly sensitive hawk; the message was chosen so that no one could decrypt the message by guessing the plaintext and showing that it encrypted to the ciphertext). For more details of this factorization, see [Atkins et al.]. If you want to see how the decryption works once the factorization is known, see Example 28 in the Computer Appendices.