RSA numbers are composite numbers having exactly two prime factors (i.e., so-called semiprimes) that have been listed in the Factoring Challenge of RSA Security and have been particularly chosen to be difficult to factor.

While RSA numbers are much smaller than the largest known primes, their factorization is significant because of the curious property of numbers that proving or disproving a number to be prime ("primality testing") seems to be much easier than actually identifying the factors of a number ("prime factorization"). Thus, while it is trivial to multiply two large numbers p and q together, it can be extremely difficult to determine the factors if only their product pq is given. With some ingenuity, this property can be used to create practical and efficient encryption systems for electronic data.

RSA Laboratories sponsors the RSA Factoring Challenge to encourage research into computational number theory and the practical difficulty of factoring large integers, and because it can be helpful for users of the RSA encryption public-key cryptography algorithm for choosing suitable key lengths for an appropriate level of security. A cash prize is awarded to the first person to factor each challenge number.

RSA numbers were originally spaced at intervals of 10 decimal digits between 100 and 500 digits, and prizes were awarded according to a complicated formula. These original numbers were named according to the number of decimal digits, so RSA-100 was a hundred-digit number. As computers and algorithms became faster, the unfactored challenge numbers were removed from the prize list and replaced with a set of numbers with fixed cash prizes. At this point, the naming convention was also changed so that the trailing number would indicate the number of digits in the binary representation of the number. Hence, RSA-576 has 576 binary digits, which translates to 174 digits in decimal.

RSA numbers received widespread attention when a 129-digit number known as RSA-129 was used by R. Rivest, A. Shamir, and L. Adleman to publish one of the first public-key messages together with a $100 reward for the message's decryption (Gardner 1977). Despite widespread belief at the time that the message encoded by RSA-129 would take millions of years to break, it was factored in 1994 using a distributed computation which harnessed networked computers spread around the globe performing a multiple polynomial quadratic sieve (Leutwyler 1994). The result of all the concentrated number crunching was decryption of the encoded message to yield the profound plaintext message "The magic words are squeamish ossifrage." (For the benefit of non-ornithologists, an ossifrage is a rare predatory vulture found in the mountains of Europe.) The corresponding factorization (into a 64-digit number and a 65-digit number) is

(Leutwyler 1994, Cipra 1995).

On Feb. 2, 1999, a group led by H. te Riele completed factorization of RSA-140 into two 70-digit primes. In a preprint dated April 16, 2004, Aoki et al. factored RSA-150 into two 75-digit primes. On Aug. 22, 1999, a group led by H. te Riele completed factorization of RSA-155 into two 78-digit primes (te Riele 1999b, Peterson 1999). On December 2, Jens Franke circulated an email announcing factorization of the smallest prize number RSA-576 (Weisstein 2003). This factorization into two 87-digit factors was accomplished using a prime factorization algorithm known as the general number field sieve (GNFS).

As the following table shows, RSA-640 to RSA-2048 remain open, carrying awards from to to whoever is clever and persistent enough to track them down. A list of the open Challenge numbers may be downloaded from RSA or in the form of a Mathematica package from the MathWorld package archive.

Number Field Sieve, Prime Factorization, RSA Encryption, Semiprime