RSA Laboratories (which is an initialism of the creators of the technique; Rivest, Shamir and Adleman) published a number of semiprimes with 100 to 617 decimal digits. Cash prizes of varying size, up to US$200,000 (and prizes up to $20,000 awarded), were offered for factorization of some of them. The smallest RSA number was factored in a few days. Most of the numbers have still not been factored and many of them are expected to remain unfactored for many years to come. As of February 2020[update], the smallest 23 of the 54 listed numbers have been factored.
While the RSA challenge officially ended in 2007, people are still attempting to find the factorizations. According to RSA Laboratories, "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."[2] Some of the smaller prizes had been awarded at the time. The remaining prizes were retracted.
The first RSA numbers generated, from RSA-100 to RSA-500, were labeled according to their number of decimal digits. Later, beginning with RSA-576, binary digits are counted instead. An exception to this is RSA-617, which was created before the change in the numbering scheme. The numbers are listed in increasing order below.
Note: until work on this article is finished, please check both the table and the list, since they include different values and different information.
835 mips years run by Arjen K. Lenstra (45.503%), Bruce Dodson (30.271%), Thomas Denny (22.516%), Mark Manasse (1.658%), and Walter Lioen and Herman te Riele (0.049%)
sieving: estimated 500 mips years, run by Bruce Dodson (28.37%), Peter L. Montgomery and Marije Elkenbracht-Huizing (27.77%), Arjen K. Lenstra (19.11%), WWW contributors (17.17% ), Matt Fante (4.36%), Paul Leyland (1.66%), Damian Weber and Joerg Zayer (1.56%)
matrix (67.5 hours on the Cray-C90 at SARA, Amsterdam) and square root (48 hours per dependency on an SGI Challenge processor) run by Peter L. Montgomery and Marije Elkenbracht-Huizing
GNFS with line (by CWI; 45%) and lattice (by Arjen K. Lenstra; 55%) sieving, and a polynomial selection method by Brian Murphy and Peter L. Montgomery; and blocked Lanczos and square root by Peter L. Montgomery
polynomial selection: 2000 CPU hours on four 250 MHZ SGI Origin 2000 processors at CWI
sieving: 8.9 CPU-years on about 125 SGI and Sun workstations running at 175 MHZ on average, and on about 60 PCs running at 300 MHZ on average; approximately equivalent to 1500 mips years; run by Peter L. Montgomery, Stefania Cavallar, Herman J.J. te Riele, and Walter M. Lioen (36.8%), Paul Leyland (28.8%), Bruce Dodson (26.6%), Paul Zimmermann (5.4%), and Arjen K. Lenstra (2.5%).
matrix: 100 hours on the Cray-C916 at SARA, Amsterdam
square root: four different dependencies were run in parallel on four 250 MHZ SGI Origin 2000 processors at CWI; three of them found the factors of RSA-140 after 14.2, 19.0 and 19.0 CPU-hours
eleven weeks (including four weeks for polynomial selection, one month for sieving, one week for data filtering and matrix construction, five days for the matrix, and 14.2 hours to find the factors using the square root)
the matrix had 4671181 rows and 4704451 columns and weight 151141999 (32.36 nonzeros per row)[3]
polynomial selection run by Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson; Dodson found the one that was used
sieving: 35.7 CPU-years in total, on about one hundred and sixty 175-400 MHz SGI and Sun workstations, eight 250 MHz SGI Origin 2000 processors, one hundred and twenty 300-450 MHz Pentium II PCs, and four 500 MHz Digital/Compaq boxes; approximately equivalent to 8000 mips years; run by Alec Muffett (20.1% of relations, 3057 CPU days), Paul Leyland (17.5%, 2092 CPU days), Peter L. Montgomery and Stefania Cavallar (14.6%, 1819 CPU days), Bruce Dodson (13.6%, 2222 CPU days), Francois Morain and Gerard Guillerm (13.0%, 1801 CPU days), Joel Marchand (6.4%, 576 CPU days), Arjen K. Lenstra (5.0%, 737 CPU days), Paul Zimmermann (4.5%, 252 CPU days), Jeff Gilchrist (4.0%, 366 CPU days), Karen Aardal (0.65%, 62 CPU days), and Chris and Craig Putnam (0.56%, 47 CPU days)
matrix: 224 hours on one CPU of the Cray-C916 at SARA, Amsterdam
square root: four 300 MHz R12000 processors of a 24-processor SGI Origin 2000 at CWI; the successful one took 39.4 CPU-hours and the others took 38.3, 41.9, and 61.6 CPU-hours
9 weeks for polynomial selection, plus 5.2 months for the rest (including 3.7 months for sieving, about 1 month for data filtering and matrix construction, and 10 days for the matrix)
the polynomials were 119377138320*x^5 - 80168937284997582*y*x^4 - 66269852234118574445*y^2*x^3 + 11816848430079521880356852*y^3*x^2 + 7459661580071786443919743056*y^4*x - 40679843542362159361913708405064*y^5 and x - 39123079721168000771313449081*y (this pair has a yield of relations approximately 13.5 times that of a random polynomial selection); 124722179 relations were collected in the sieving stage; the matrix had 6699191 rows and 6711336 columns and weight 417132631 (62.27 nonzeros per row).[3]
It takes four hours to repeat this factorization using the program Msieve on a 2200 MHz Athlon 64 processor.
The number can be factorized in 72 minutes on overclocked to 3.5 GHz Intel Core2 Quad q9300, using GGNFS and Msieve binaries running by distributed version of the factmsieve Perl script.[6]
RSA-110
RSA-110 has 110 decimal digits (364 bits), and was factored in April 1992 by Arjen K. Lenstra and Mark S. Manasse in approximately one month.[4][5]
The number can be factorized in less than four hours on overclocked to 3.5 GHz Intel Core2 Quad q9300, using GGNFS and Msieve binaries running by distributed version of the factmsieve Perl script.[6]
RSA-120 has 120 decimal digits (397 bits), and was factored in June 1993 by Thomas Denny, Bruce Dodson, Arjen K. Lenstra, and Mark S. Manasse.[7] The computation took under three months of actual computer time.
The factoring challenge included a message encrypted with RSA-129. When decrypted using the factorization the message was revealed to be "The Magic Words are Squeamish Ossifrage".
In 2015, RSA-129 was factored in about one day, with the CADO-NFS open source implementation of number field sieve, using a commercial cloud computing service for about $30.[10]
RSA-130
RSA-130 has 130 decimal digits (430 bits), and was factored on April 10, 1996, by a team led by Arjen K. Lenstra and composed of Jim Cowie, Marije Elkenbracht-Huizing, Wojtek Furmanski, Peter L. Montgomery, Damian Weber and Joerg Zayer.[11]
which has a root of 12574411168418005980468 modulo RSA-130.
RSA-140
RSA-140 has 140 decimal digits (463 bits), and was factored on February 2, 1999, by a team led by Herman te Riele and composed of Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Paul Leyland, Walter Lioen, Peter L. Montgomery, Brian Murphy and Paul Zimmermann.[12][13]
The factorization was found using the Number Field Sieve algorithm and an estimated 2000 MIPS-years of computing time.
RSA-150
RSA-150 has 150 decimal digits (496 bits), and was withdrawn from the challenge by RSA Security. RSA-150 was eventually factored into two 75-digit primes by Aoki et al. in 2004 using the general number field sieve (GNFS), years after bigger RSA numbers that were still part of the challenge had been solved.
RSA-155 has 155 decimal digits (512 bits), and was factored on August 22, 1999, in a span of six months, by a team led by Herman te Riele and composed of Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen, Peter L. Montgomery, Brian Murphy, Karen Aardal, Jeff Gilchrist, Gerard Guillerm, Paul Leyland, Joel Marchand, François Morain, Alec Muffett, Craig Putnam, Chris Putnam and Paul Zimmermann.[14][15]
RSA-170 has 170 decimal digits (563 bits) and was first factored on December 29, 2009, by D. Bonenberger and M. Krone from Fachhochschule Braunschweig/Wolfenbüttel.[18] An independent factorization was completed by S. A. Danilov and I. A. Popovyan two days later.[19]
RSA-576 has 174 decimal digits (576 bits), and was factored on December 3, 2003, by J. Franke and T. Kleinjung from the University of Bonn.[20][21][22] A cash prize of $10,000 was offered by RSA Security for a successful factorization.
RSA-180 has 180 decimal digits (596 bits), and was factored on May 8, 2010, by S. A. Danilov and I. A. Popovyan from Moscow State University, Russia.[23]
The factorization was found using the general number field sieve algorithm implementation running on three Intel Core i7 PCs.
RSA-190
RSA-190 has 190 decimal digits (629 bits), and was factored on November 8, 2010, by I. A. Popovyan from Moscow State University, Russia, and A. Timofeev from CWI, Netherlands.[24]
RSA-640 has 193 decimal digits (640 bits). A cash prize of US$20,000 was offered by RSA Security for a successful factorization. On November 2, 2005, F. Bahr, M. Boehm, J. Franke and T. Kleinjung of the German Federal Office for Information Security announced that they had factorized the number using GNFS as follows:[25][26][27]
The CPU time spent on finding these factors by a collection of parallel computers amounted – very approximately – to the equivalent of 75 years work for a single 2.2 GHzOpteron-based computer.[28] Note that while this approximation serves to suggest the scale of the effort, it leaves out many complicating factors; the announcement states it more precisely.
RSA-210
RSA-210 has 210 decimal digits (696 bits) and was factored in September 2013 by Ryan Propper:[30]
RSA-704 has 212 decimal digits (704 bits), and was factored by Shi Bai, Emmanuel Thomé and Paul Zimmermann.[31] The factorization was announced July 2, 2012.[32] A cash prize of US$30,000 was previously offered for a successful factorization.
RSA-220 has 220 decimal digits (729 bits), and was factored by S. Bai, P. Gaudry, A. Kruppa, E. Thomé and P. Zimmermann. The factorization was announced on May 13, 2016.[33]
RSA-768 has 232 decimal digits (768 bits), and was factored on December 12, 2009, over the span of two years, by Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Joppe W. Bos, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann.[38]
The CPU time spent on finding these factors by a collection of parallel computers amounted approximately to the equivalent of almost 2000 years of computing on a single-core 2.2 GHz AMD Opteron-based computer.[38]
RSA-240
RSA-240 has 240 decimal digits (795 bits), and was factored in November 2019 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann.[39]
The CPU time spent on finding these factors amounted to approximately 900 core-years on a 2.1 GHz Intel Xeon Gold 6130 CPU. Compared to the factorization of RSA-768, the authors estimate that better algorithms sped their calculations by a factor of 3–4 and faster computers sped their calculation by a factor of 1.25–1.67.
RSA-250
RSA-250 has 250 decimal digits (829 bits), and was factored in February 2020 by Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann. The announcement of the factorization occurred on February 28.
The factorisation of RSA-250 utilised approximately 2700 CPU core-years, using a 2.1 GHz Intel Xeon Gold 6130 CPU as a reference. The computation was performed with the Number Field Sieve algorithm, using the open source CADO-NFS software.
RSA-896 has 270 decimal digits (896 bits), and has not been factored so far. A cash prize of $75,000 was previously offered for a successful factorization.
^RSA Laboratories. "RSA Factoring Challenge". Archived from the original on September 21, 2013. Retrieved August 5, 2008.((cite web)): CS1 maint: unfit URL (link)
^ abcdefghiRSA Factoring Challenge Administrator (challenge-administrator@majordomo.rsasecurity.com) (January 30, 2002) [March 5, 1999]. "RSA Honor Roll". challenge-rsa-honor-roll@rsa.com (Mailing list). Archived from the original on September 9, 2023 – via Ray Ontko.
^Denny, T.; Dodson, B.; Lenstra, A. K.; Manasse, M. S. (1994). "On the factorization of RSA-120". In Stinson, Douglas R. (ed.). Advances in Cryptology — CRYPTO' 93. Lecture Notes in Computer Science. Vol. 773. Berlin, Heidelberg: Springer (published July 13, 2001). pp. 166–174. doi:10.1007/3-540-48329-2_15. ISBN978-3-540-48329-8 – via SpringerLink.
^Atkins, Derek; Graff, Michael; Lenstra, Arjen K.; Leyland, Paul C. "The Magic Words Are Squeamish Ossifrage". Derek Atkins (PostScript document). Archived from the original on September 9, 2023. Retrieved November 24, 2009 – via Massachusetts Institute of Technology.
^Lenstra, Arjen K.; Cowie, Jim; Elkenbracht-Huizing, Marije; Furmanski, Wojtek; Montgomery, Peter L.; Weber, Damian; Zayer, Joerg (April 12, 1996) [April 11, 1996]. Caldwell, Chris (ed.). "Factorization of RSA-130". NMBRTHRY (Mailing list). PrimePages: prime number research records and results. Archived from the original on September 2, 2023. Retrieved March 10, 2008 – via Notes, Proofs and other Comments.
^Riele, Herman te; Cavallar, Stefania; Dodson, Bruce; Lenstra, Arjen; Leyland, Paul; Lioen, Walter; Montgomery, Peter; Murphy, Brian; Zimmermann, Paul (February 4, 1999) [February 3, 1999]. "Factorization of RSA-140 using the Number Field Sieve". Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU> (Mailing list). North Dakota University System. Archived from the original on December 8, 2004. Retrieved March 10, 2008.
^"RSA-140 is factored!". Other Activities: Cryptographic Challenges: The RSA Factoring Challenge. RSA Laboratories. RSA Security. Archived from the original on December 30, 2006. Retrieved March 10, 2008.
^"RSA-155 is factored!". Other Activities: Cryptographic Challenges: The RSA Factoring Challenge. RSA Laboratories. RSA Security. Archived from the original on December 30, 2006. Retrieved March 10, 2008.
^Bahr, F.; Franke, J.; Kleinjung, T.; Lochter, M.; Böhm, M. (April 1, 2003). Franke, Jens (ed.). "RSA-160". Paul Zimmermann, Laboratoire Lorrain de Recherche en Informatique et ses Applications. Archived from the original on September 2, 2023. Retrieved March 10, 2008. We have factored RSA160 by gnfs.
