RSA Laboratories

2.3.6 What is the RSA Factoring Challenge?

The RSA Factoring Challenge was started in March 1991 by RSA Data Security (now RSA Security) to keep abreast of the state of the art in factoring. Since its inception, well over a thousand numbers have been factored, with the factorers returning valuable information on the methods they used to complete the factorizations. The Factoring Challenge provides one of the largest test-beds for factoring implementations and provides one of the largest collections of factoring results from many different experts worldwide. In short, this vast pool of information gives us an excellent opportunity to compare the effectiveness of different factoring techniques as they are implemented and used in practice. Since the security of the RSA public-key cryptosystem relies on the inability to factor large numbers of a special type, the cryptographic significance of these results is self-evident.

The most important result thus far is the factorization of RSA-155 (a number with 155 digits), which was completed in August 1999 after seven months. A group consisting of, among several others, Arjen K. Lenstra and Herman te Riele performed the necessary computations on 300 workstations and PCs. The factorization of this 512-bit number is crucial as 512 is the default key size used for the major part of the e-commerce on Internet. The result indicates that a well-organized group of users such as (see Question 2.4.4) might be able to break a 512-bit key in just a couple of days.

Yet, the practical significance of the factorization of RSA-155 should not be exaggerated. The result is very impressive, but the cost for breaking a 512-bit key is still high enough to prevent potential attackers to apply the techniques on a wider basis. Consider it as a reminder of the importance of choosing sufficiently large key sizes; choosing key sizes of at least 768 bits was recommended by RSA Laboratories long before this factorization.

As a curiosity, we mention that the RSA-155 factorization is


For more information about the RSA Factoring Challenges, see

The challenge is administered by RSA Security with quarterly cash awards. Send e-mail to for more information. For an analysis of early results from the factoring challenge, see [FR95].

A predecessor to the RSA Factoring Challenge is RSA-129. This number is a 129-digit (426-bit) integer published in Martin Gardner's column in Scientific American in 1977; it is not part of the RSA Factoring Challenge. A prize of $100 was offered to anybody able to factor the number; it was factored in March 1994 by Atkins, Graff, Lenstra, and Leyland [AGL95] after eight months of extensive computations.

Top of the page