The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They published a list of semiprimes (numbers with exactly two prime factors) known as the RSA numbers, with a cash prize for the successful factorization of some of them. The smallest of them, a 100-decimal digit number called RSA-100 was factored by April 1, 1991. Many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time, however advances in quantum computers make this prediction uncertain due to Shor's algorithm.
In 2001, RSA Laboratories expanded the factoring challenge and offered prizes ranging from $10,000 to $200,000 for factoring numbers from 576 bits up to 2048 bits.
The RSA Factoring Challenges ended in 2007. RSA Laboratories stated: "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active." When the challenge ended in 2007, only RSA-576 and RSA-640 had been factored from the 2001 challenge numbers.
The factoring challenge was intended to track the cutting edge in integer factorization. A primary application is for choosing the key length of the RSA public-key encryption scheme. Progress in this challenge should give an insight into which key sizes are still safe and for how long. As RSA Laboratories is a provider of RSA-based products, the challenge was used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength.
The RSA numbers were generated on a computer with no network connection of any kind. The computer's hard drive was subsequently destroyed so that no record would exist, anywhere, of the solution to the factoring challenge.
The first RSA numbers generated, RSA-100 to RSA-500 and RSA-617, were labeled according to their number of decimal digits; the other RSA numbers (beginning with RSA-576) were generated later and labelled according to their number of binary digits. The numbers in the table below are listed in increasing order despite this shift from decimal to binary.
The mathematics RSA Laboratories states that: for each RSA number n, there exist prime numbers p and q such that n = p × q.
The problem is to find these two primes, given only n.
The prizes and records The following table gives an overview over all RSA numbers. Note that the RSA Factoring Challenge ended in 2007 and no further prizes will be awarded for factoring the higher numbers. The challenge numbers in white lines are part of the original challenge and are expressed in base 10, while the challenge numbers in yellow lines are part of the 2001 expansion and are expressed in base 2 RSA number Decimal digits Binary digits Cash prize offered Factored on Factored by RSA-100 100 330 US$1,000 April 1, 1991RSA Honor Roll Arjen K. Lenstra RSA-110 110 364 US$4,429 April 14, 1992 Arjen K. Lenstra and M.S. Manasse RSA-120 120 397 US$5,898 July 9, 1993 T. Denny et al. RSA-129 129 426 US$100 April 26, 1994 Arjen K. Lenstra et al. RSA-130 130 430 US$14,527 April 10, 1996 Arjen K. Lenstra et al. RSA-140 140 463 US$17,226 February 2, 1999 Herman te Riele et al. RSA-150 150 496 April 16, 2004 Kazumaro Aoki et al. RSA-155 155 512 US$9,383 August 22, 1999 Herman te Riele et al. RSA-160 160 530 April 1, 2003 Jens Franke et al., University of Bonn RSA-170 170 563 December 29, 2009 D. Bonenberger and M. Krone RSA-576 174 576 US$10,000 December 3, 2003 Jens Franke et al., University of Bonn RSA-180 180 596 May 8, 2010 S. A. Danilov and I. A. Popovyan, Moscow State University RSA-190 190 629 November 8, 2010 A. Timofeev and I. A. Popovyan RSA-640 193 640 US$20,000 November 2, 2005 Jens Franke et al., University of Bonn RSA-200 200 663 May 9, 2005 Jens Franke et al., University of Bonn RSA-210 210 696 September 26, 2013RSA-210 factored, mersenneforum.org Ryan Propper RSA-704 212 704 US$30,000 July 2, 2012 Shi Bai, Emmanuel Thomé and Paul Zimmermann RSA-220 220 729 May 13, 2016 S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann RSA-230 230 762 August 15, 2018 Samuel S. Gross, Noblis, Inc. RSA-232 232 768 February 17, 2020INM RAS news N. L. Zamarashkin, D. A. Zheltkov and S. A. Matveev. RSA-768 232 768 US$50,000 December 12, 2009 Thorsten Kleinjung et al. RSA-240 240 795 December 2, 2019 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann RSA-250 250 829 February 28, 2020 F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann RSA-260 260 862 September 3, 2026 Eric Lu, Cognition RSA-270 270 895 RSA-896 270 896 US$75,000 September 19, 2026 Stephen A. Weis RSA-280 280 928 RSA-290 290 962 RSA-300 300 995 RSA-309 309 1024 RSA-1024 309 1024 US$100,000 RSA-310 310 1028 RSA-320 320 1061 RSA-330 330 1094 RSA-340 340 1128 RSA-350 350 1161 RSA-360 360 1194 RSA-370 370 1227 RSA-380 380 1261 RSA-390 390 1294 RSA-400 400 1327 RSA-410 410 1360 RSA-420 420 1393 RSA-430 430 1427 RSA-440 440 1460 RSA-450 450 1493 RSA-460 460 1526 RSA-1536 463 1536 US$150,000 RSA-470 470 1559 RSA-480 480 1593 RSA-490 490 1626 RSA-500 500 1659 RSA-617 617 2048 RSA-2048 617 2048 US$200,000
See also RSA numbers, decimal expansions of the numbers and known factorizations LCS35 The Magic Words are Squeamish Ossifrage, the solution found in 1993 to another RSA challenge posed in 1977 RSA Secret-Key Challenge Integer factorization records Jevon's number
Notes