RSA numbers

In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that were part of the RSA Factoring Challenge. The challenge was to find the prime factors of each number. It was created by RSA Laboratories in March 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers. The challenge was ended in 2007.^[1]

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.


name	dec digits	first solver
name	dec digits	date	algorithm	compute power	calendar time
RSA-100		1991-04-01	ppmpqs by Mark Manasse and Arjen K. Lenstra	approx. 7 MIP-Years
RSA-110		1992-04-14	ppmpqs by Arjen K. Lenstra	one month on 5/8 of a 16K MasPar
RSA-120		1993-06-09	ppmpqs	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%)
RSA-129	129	1994-04-26	ppmpqs	approximately 5000 mips years run by Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul Leyland, and more than 600 volunteers
RSA-130		1996-04-10	General Number Field Sieve with lattice sieving implementations by Bellcore, CWI, and Saarbruecken; and blocked Lanczos and square root by Peter L. Montgomery	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
RSA-140		1999-02-02	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)
RSA-155		1999-08-22	GNFS with line (29%) and lattice (71%) sieving, and a polynomial selection method written by Brian Murphy and Peter L. Montgomery, ported by Arjen Lenstra to use his multiple precision arithmetic code (LIP); and blocked Lanczos and square root by Peter L. Montgomery	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)

Contents
RSA-100 RSA-110 RSA-120 RSA-129 RSA-130 RSA-140 RSA-150 RSA-155 RSA-160	RSA-170 RSA-576 RSA-180 RSA-190 RSA-640 RSA-200 RSA-210 RSA-704 RSA-220	RSA-230 RSA-232 RSA-768 RSA-240 RSA-250 RSA-260 RSA-270 RSA-896 RSA-280	RSA-290 RSA-300 RSA-309 RSA-1024 RSA-310 RSA-320 RSA-330 RSA-340 RSA-350	RSA-360 RSA-370 RSA-380 RSA-390 RSA-400 RSA-410 RSA-420 RSA-430 RSA-440	RSA-450 RSA-460 RSA-1536 RSA-470 RSA-480 RSA-490 RSA-500 RSA-617 RSA-2048
See also Notes References External links

^ RSA Laboratories. "RSA Factoring Challenge". Archived from the original on September 21, 2013. Retrieved August 5, 2008.{{cite web}}: CS1 maint: unfit URL (link)
^ RSA Laboratories. "The RSA Factoring Challenge FAQ". Archived from the original on September 21, 2013. Retrieved August 5, 2008.{{cite web}}: CS1 maint: unfit URL (link)

[RSAfactoring-challenge-1] RSA Laboratories. "RSA Factoring Challenge". Archived from the original on September 21, 2013. Retrieved August 5, 2008.{{cite web}}: CS1 maint: unfit URL (link)

[RSAfactoring-challenge-faq-2] RSA Laboratories. "The RSA Factoring Challenge FAQ". Archived from the original on September 21, 2013. Retrieved August 5, 2008.{{cite web}}: CS1 maint: unfit URL (link)

[1]

[2]