Editing RSA numbers (section)

{{Short description|Set of large semiprimes}}
{{Use mdy dates|date=October 2023}}
In [[mathematics]], the '''RSA numbers''' are a set of large [[semiprimes]] (numbers with exactly two [[prime factor]]s) that were part of the [[RSA Factoring Challenge]]. The challenge was to find the prime factors of each number. It was created by [[RSA Security|RSA Laboratories]] in March 1991 to encourage research into [[computational number theory]] and the practical difficulty of [[integer factorization|factoring]] large [[integer]]s. The challenge was ended in 2007.<ref name=RSAfactoring-challenge>{{cite web |title=RSA Factoring Challenge |author=RSA Laboratories |accessdate=2008-08-05 |url=http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm |url-status=usurped |archive-url=https://web.archive.org/web/20130921043459/http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm |archive-date=2013-09-21}}</ref>

[[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 [[United States dollar|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|2020|02}}, 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."<ref name=RSAfactoring-challenge-faq>{{cite web |title=The RSA Factoring Challenge FAQ |author=RSA Laboratories |accessdate=2008-08-05 |url=http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm |url-status=usurped |archive-url=https://web.archive.org/web/20130921043454/http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm |archive-date=2013-09-21}}</ref> 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 numeral system|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.
{{sticky header}}

Note: until work on this article is finished, please check both the table and the list, since they include different values and different information.
{| class="wikitable sortable sticky-header-multi" style="table-layout: fixed; overflow-wrap: anywhere;"
|+
! rowspan="2" style="width:5ch" |name
! rowspan="2" style="width:5ch" |dec digits
! colspan="4" |first solver
|-
! style="width:5ch"|date
! |algorithm
! |compute power
! |calendar time
|-
|RSA-100
|
|1991-04-01
|[[Quadratic sieve#Implementations|ppmpqs]] by [[Mark Manasse]] and [[Arjen Lenstra|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|General Number Field Sieve]] with [[lattice sieving]] implementations by Bellcore, [[Centrum Wiskunde & Informatica|CWI]], and Saarbruecken; and blocked [[Lanczos algorithm|Lanczos]] and [[Square root of a matrix|square root]] by [[Peter Montgomery (mathematician)|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
|[[General number field sieve|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 algorithm|Lanczos]] and [[Square root of a matrix|square root]] by [[Peter Montgomery (mathematician)|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 te Riele|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
|[[General number field sieve|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|multiple precision arithmetic]] code (LIP); and blocked [[Lanczos algorithm|Lanczos]] and [[Square root of a matrix|square root]] by [[Peter Montgomery (mathematician)|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&nbsp;MHz SGI and Sun workstations, eight 250&nbsp;MHz SGI Origin 2000 processors, one hundred and twenty 300-450&nbsp;MHz Pentium II PCs, and four 500&nbsp;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&nbsp;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)
|}
{| id="toc" class="toc" summary="Contents"
|-
! colspan="6" | {{MediaWiki:Toc}}
|-
| style="width:16%; vertical-align:top; padding-left: 6px; padding-right:6px"|
* [[#RSA-100|RSA-100]]
* [[#RSA-110|RSA-110]]
* [[#RSA-120|RSA-120]]
* [[#RSA-129|RSA-129]]
* [[#RSA-130|RSA-130]]
* [[#RSA-140|RSA-140]]
* [[#RSA-150|RSA-150]]
* [[#RSA-155|RSA-155]]
* [[#RSA-160|RSA-160]]
| style="width:16%; vertical-align:top; padding-left: 6px; padding-right:6px"|
* [[#RSA-170|RSA-170]]
* [[#RSA-576|RSA-576]]
* [[#RSA-180|RSA-180]]
* [[#RSA-190|RSA-190]]
* [[#RSA-640|RSA-640]]
* [[#RSA-200|RSA-200]]
* [[#RSA-210|RSA-210]]
* [[#RSA-704|RSA-704]]
* [[#RSA-220|RSA-220]]
| style="width:16%; vertical-align:top; padding-left: 6px; padding-right:6px"|
* [[#RSA-230|RSA-230]]
* [[#RSA-232|RSA-232]]
* [[#RSA-768|RSA-768]]
* [[#RSA-240|RSA-240]]
* [[#RSA-250|RSA-250]]
* [[#RSA-260|RSA-260]]
* [[#RSA-270|RSA-270]]
* [[#RSA-896|RSA-896]]
* [[#RSA-280|RSA-280]]
| style="width:16%; vertical-align:top; padding-left: 6px; padding-right:6px"|
* [[#RSA-290|RSA-290]]
* [[#RSA-300|RSA-300]]
* [[#RSA-309|RSA-309]]
* [[#RSA-1024|RSA-1024]]
* [[#RSA-310|RSA-310]]
* [[#RSA-320|RSA-320]]
* [[#RSA-330|RSA-330]]
* [[#RSA-340|RSA-340]]
* [[#RSA-350|RSA-350]]
| style="width:16%; vertical-align:top; padding-left: 6px; padding-right:6px"|
* [[#RSA-360|RSA-360]]
* [[#RSA-370|RSA-370]]
* [[#RSA-380|RSA-380]]
* [[#RSA-390|RSA-390]]
* [[#RSA-400|RSA-400]]
* [[#RSA-410|RSA-410]]
* [[#RSA-420|RSA-420]]
* [[#RSA-430|RSA-430]]
* [[#RSA-440|RSA-440]]
| style="width:16%; vertical-align:top; padding-left: 6px; padding-right:6px"|
* [[#RSA-450|RSA-450]]
* [[#RSA-460|RSA-460]]
* [[#RSA-1536|RSA-1536]]
* [[#RSA-470|RSA-470]]
* [[#RSA-480|RSA-480]]
* [[#RSA-490|RSA-490]]
* [[#RSA-500|RSA-500]]
* [[#RSA-617|RSA-617]]
* [[#RSA-2048|RSA-2048]]
|-
| colspan="6" | &nbsp; [[#See also|See also]] &nbsp;&nbsp;&nbsp; [[#Notes|Notes]] &nbsp;&nbsp;&nbsp; [[#References|References]] &nbsp;&nbsp;&nbsp; [[#External links|External links]]
__NOTOC__
|}