From challenge-administrator@majordomo.rsasecurity.com Wed Jan 30 16:03:25 2002 Return-Path: Received: from pathfinder.securitydynamics.com (securecare.securitydynamics.com [205.181.76.19]) by shire.ontko.com (8.9.3/8.9.3/Debian 8.9.3-21) with SMTP id QAA00358 for ; Wed, 30 Jan 2002 16:03:24 -0500 X-Authentication-Warning: shire.ontko.com: Host securecare.securitydynamics.com [205.181.76.19] claimed to be pathfinder.securitydynamics.com Received: from cameos.rsasecurity.com by pathfinder.securitydynamics.com via smtpd (for shire.ontko.com [199.164.165.1]) with SMTP; 31 Jan 2002 00:00:51 UT Received: (from daemon@localhost) by cameos.majordomo.rsasecurity.com (8.8.8+Sun/notrash) id PAA23141; Wed, 30 Jan 2002 15:54:43 -0500 (EST) Date: Wed, 30 Jan 2002 15:54:43 -0500 (EST) Message-Id: <200201302054.PAA23141@cameos.majordomo.rsasecurity.com> From: challenge-administrator@majordomo.rsasecurity.com (RSA Factoring Challenge Administrator) To: rayo@ontko.com X-IMAPbase: 1128097135 1 Status: RO X-Status: X-Keywords: X-UID: 1 RSA Honor Roll -------------- As of March 5, 1999 RSA-100 Factors: 40094690950920881030683735292761468389214899724061 * 37975227936943673922808872755445627854565536638199 Date: April 1, 1991 Method: ppmpqs Time: Approx. 7 MIP-Years Name: Mark Manasse, Arjen K. Lenstra Email: msm@src.dec.com, lenstra@flash.bellcore.com Recd: April 1, 1991 --------------------------------------------------------------- RSA-110 Factors: 6122421090493547576937037317561418841225758554253106999 * 5846418214406154678836553182979162384198610505601062333 Date: April 14, 1992 Method: ppmpqs Time: one month on 5/8 of a 16K MasPar Name: Arjen K. Lenstra Email: lenstra@bellcore.com Recd: April 14, 1992 --------------------------------------------------------------- RSA-120 Factors: 327414555693498015751146303749141488063642403240171463406883 * 693342667110830181197325401899700641361965863127336680673013 Date: June 9, 1993 Method: ppmpqs Time: 835 mips years Name: Arjen K. Lenstra (45.503%), Bruce Dodson (30.271%), Thomas Denny (22.516%), Mark Manasse (1.658%), Walter Lioen and Herman te Riele (0.049%) Email: lenstra@bellcore.com Recd: June 9, 1993 --------------------------------------------------------------- RSA-129 represents the "RSA challenge" published in the August 1977 issue of Scientific American (in Martin Gardner's column). The $100 prize was won by factoring the RSA modulus published there, which is: RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 (129 digits, checksum = 105443) Please note that this number is NOT part of the current RSA Factoring Challenge and is included here for informational purposes only. Factors: 3490529510847650949147849619903898133417764638493387843990820577 * 32769132993266709549961988190834461413177642967992942539798288533 Date: April 1994 Method: ppmpqs Time: Approximately 5000 mips years Name: Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul Leyland, and more than 600 volunteers Email: lenstra@bellcore.com Recd: April 26, 1994 --------------------------------------------------------------- RSA-130 Factors: 39685999459597454290161126162883786067576449112810064832555157243 * 45534498646735972188403686897274408864356301263205069600999044599 Date: April 10, 1996 Method: GNFS with lattice sieving, combined with Peter L. Montgomery's blocked Lanczos and square root algorithms Name: - Sieving: 28.37% Bruce Dodson (B) 27.77% Peter L. Montgomery and Marije Elkenbracht-Huizing (B,C) 19.11% Arjen K. Lenstra (B) 17.17% WWW contributors (B) 4.36% Matt Fante (B) 1.66% Paul Leyland (B) 1.56% Damian Weber and Joerg Zayer (S) sieving code from Bellcore (B), CWI (C), and Saarbruecken (S) - Matrix and square root: Peter L. Montgomery and Marije Elkenbracht-Huizing Time: - Sieving: 500 mips years (based on timing using code (B) on >=24M workstations) - Matrix: 67.5 hours on the Cray-C90 at SARA, Amsterdam - square root: 48 hours per dependency on an SGI Challenge processor factorization found at the third trial Email: lenstra@bellcore.com Recd: April 10, 1996 --------------------------------------------------------------- RSA-140 Factors: 3398717423028438554530123627613875835633986495969597423490929302771479 * 6264200187401285096151654948264442219302037178623509019111660653946049 Date: February 2, 1999 Method: the General Number Field Sieve, with a new polynomial selection method developed by Brian Murphy and Peter L. Montgomery, with line sieving (45%) and with lattice sieving (55%), and with Peter L. Montgomery's blocked Lanczos and square root algorithms; both factors were proved to be prime with two different primality proving algorithms Time: * Polynomial selection: 2000 CPU hours on four 250 MHZ SGI Origin 2000 processors at CWI; calendar time for the polynomial selection: four weeks * 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; this CPU-effort is estimated to be equivalent to approximately 1500 mips years; calendar time for the sieving: one month; 66933395 relations were collected by five sites, distributed as follows: (C: using line sieving code from CWI, L: using lattice sieving code from Arjen K. Lenstra) 36.8 % Peter L. Montgomery, Stefania Cavallar, Herman J.J. te Riele, Walter M. Lioen (C,L) 28.8 % Paul Leyland (L) 26.6 % Bruce Dodson (C,L) 5.4 % Paul Zimmermann (L) 2.5 % Arjen K. Lenstra (L) * Filtering the data, building the matrix took one calendar week * Matrix: 100 hours on the Cray-C916 at SARA, Amsterdam; the matrix had 4671181 rows and 4704451 columns, and weight 151141999 (32.36 nonzeros per row); calendar time: five days * 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 (and calendar hours), respectively (different CPU times due to the use of different parameters in one of the four jobs) * The total calendar time for factoring RSA-140 was eleven weeks Names: Herman J.J. te Riele (CWI, contact person) Stefania Cavallar, Walter M. Lioen, Peter L. Montgomery (CWI) Bruce Dodson (Lehigh University, Bethlehem, PA, USA) Arjen K. Lenstra (Citibank, Parsippany, NJ, USA and Univ. of Sydney, Australia) Paul Leyland (Microsoft, Cambridge, UK) Brian Murphy (The Australian National University, Canberra) Paul Zimmermann (Inria Lorraine and Loria, Nancy, France) Address: (contact person) Centre for Mathematics and Computer Science (CWI) Kruislaan 413, 1098 SJ Amsterdam, The Netherlands Email: herman@cwi.nl Phone: +31 20 5924106 Recd: February 2,1999 --------------------------------------------------------------- Prize Breakdown for the RSA Factoring Challenge 3rd Quarter, 1999 RSA Challenge List: ------------------ RSA-155 Factors: 102639592829741105772054196573991675900716567808038066803341933521790711307779 * 106603488380168454820927220360012878679207958575989291522270608237193062808643 Date: August 22, 1999 Method: the General Number Field Sieve, with a polynomial selection method of Brian Murphy and Peter L. Montgomery, with lattice sieving (71%) and with line sieving (29%), and with Peter L. Montgomery's blocked Lanczos and square root algorithms; Time: * Polynomial selection: The polynomial selection took approximately 100 MIPS years, equivalent to 0.40 CPU years on a 250 MHz processor. The two polynomials F_1(x,y) = 11 93771 38320 x^5 - 80 16893 72849 97582 y *x^4 - 66269 85223 41185 74445 y^2*x^3 + 1 18168 48430 07952 18803 56852 y^3*x^2 + 745 96615 80071 78644 39197 43056 y^4*x - 40 67984 35423 62159 36191 37084 05064 y^5 F_2(x,y) = x - 3912 30797 21168 00077 13134 49081 y were selected using procedures developed by Peter Montgomery and Brian Murphy for the factorisation of RSA-140. Better use was made of these procedures for the RSA-155 factorisation than for the RSA-140 factorisation. The pair (F_1, F_2) has a yield of relations approximately 13.5 times that of a random polynomial selection for RSA-155 (the corresponding figure for the RSA-140 factorisation is approximately 8). The original polynomial selection code was ported by Arjen Lenstra to use his multiple precison arithmetic package LIP. Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson ran polynomial searches for RSA-155. The above polynomial emerged from Bruce Dodson's search. Calendar time for the polynomial selection was approximately nine weeks. * Sieving: 35.7 CPU-years in total, on about 160 175-400 MHz SGI and Sun workstations, on 8 250 MHz SGI Origin 2000 processors, on 120 300-450 MHz Pentium II PCs, and on 4 500 MHz Digital/Compaq boxes; this CPU-effort is estimated to be equivalent to approximately 8000 mips years; calendar time for the sieving was 3.7 months; 124 722 179 relations were collected by eleven different sites, distributed as follows: (L: using lattice sieving code from Arjen K. Lenstra C: using line sieving code from CWI) 20.1 % (3057 CPU days) Alec Muffett (L) 17.5 % (2092) Paul Leyland (L,C) 14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L) 13.6 % (2222) Bruce Dodson (L,C) 13.0 % (1801) Francois Morain and Gerard Guillerm (L,C) 6.4 % (576) Joel Marchand (L,C) 5.0 % (737) Arjen K. Lenstra (L) 4.5 % (252) Paul Zimmermann (C) 4.0 % (366) Jeff Gilchrist (L) 0.65 % (62) Karen Aardal (L) 0.56 % (47) Chris and Craig Putnam (L) * Filtering the data and building the matrix took about a month * Matrix: 224 hours on one CPU of the Cray-C916 at SARA, Amsterdam; the matrix had 6 699 191 rows and 6 711 336 columns, and weight 417 132 631 (62.27 nonzeros per row); calendar time: ten days * Square root: Four jobs assigned one dependency each were run in parallel on separate 300 MHz R12000 processors within a 24-processor SGI Origin 2000 at CWI. One job found the factorisation after 39.4 CPU-hours, the other three jobs found the trivial factorization after 38.3, 41.9, and 61.6 CPU-hours (different CPU times are due to the use of different parameters in the four jobs). * The total calendar time for factoring RSA-155 was 5.2 months (March 17 - August 22) (excluding polynomial generation time) We could reduce this to one month sieving time and one month processing time if we had more sievers and had more experience with matrix-generation strategies. Names/ Herman J.J. te Riele (CWI Amsterdam, contact person) sites: Karen Aardal (Utrecht University, The Netherlands) Stefania Cavallar, Walter M. Lioen (CWI Amsterdam, The Netherlands) Bruce Dodson (Lehigh University, Bethlehem, PA, USA) Jeff Gilchrist (Entrust Technologies Ltd., Ottawa, Canada) Arjen K. Lenstra (Citibank, Parsippany, NJ, USA and Univ. of Sydney, Australia) Paul Leyland (Microsoft Research, Cambridge, UK) Joel Marchand (Ecole Polytechnique/CNRS, Palaiseau, France) Peter L. Montgomery (Microsoft Research, USA, and CWI) Francois Morain and Gerard Guillerm (Ecole Polytechnique, Palaiseau, France) Alec Muffett (Sun Microsystems Professional Services, Camberley, UK) Brian Murphy (The Australian National University, Canberra) Chris and Craig Putnam (USA) Paul Zimmermann (Inria Lorraine and Loria, Nancy, France) Address: (of contact person) Centre for Mathematics and Computer Science (CWI) Kruislaan 413, 1098 SJ Amsterdam, The Netherlands Email: Herman.te.Riele@cwi.nl Phone: +31 20 5924106 Fax: +31 20 5924199 --------------------------------------------------------------- $9383