Editing RSA numbers (section)

==RSA-155==
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 Lenstra|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.<ref>{{Cite mailing list |url=http://listserv.nodak.edu/scripts/wa.exe?A2=ind9908&L=nmbrthry&P=1905 |title=New factorization record: Factorization of a 512-bits RSA key using the Number Field Sieve |date=26 Aug 1999 |mailing-list=Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU> |last=Riele |first=Herman te |author-link=Herman te Riele |archive-url=https://web.archive.org/web/20041231230220/http://listserv.nodak.edu/scripts/wa.exe?A2=ind9908&L=nmbrthry&P=1905 |archive-date=2004-12-31 |url-status=dead |publisher=North Dakota University System |quote=On August 22, 1999, we found that the 512-bits number RSA-155 ... |access-date=2008-03-10}}</ref><ref>{{Cite web |title=RSA-155 is factored! |url=http://www.rsasecurity.com/rsalabs/node.asp?id=2098 |url-status=dead |archive-url=https://web.archive.org/web/20061230233723/http://www.rsasecurity.com/rsalabs/node.asp?id=2098 |archive-date=2006-12-30 |access-date=2008-03-10 |website=RSA Laboratories |publisher=RSA Security |department=Other Activities: Cryptographic Challenges: The RSA Factoring Challenge}}</ref>

The value and factorization are as follows:

 RSA-155 = 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897

 RSA-155 = 1026395928297411057720541965739916759007165678080380668033419335217907113077
           79
         × 1066034883801684548209272203600128786792079585759892915222706082371930628086
           43

The factorization was found using the [[general number field sieve]] algorithm and an estimated 8000 [[MIPS-year]]s of computing time.

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).<ref name="RSA Honor Roll" />