(original) (raw)

Date: Mon, 9 May 2005 18:05:10 +0200 (CEST) From: Thorsten Kleinjung Subject: rsa200 We have factored RSA200 by GNFS. The factors are 35324619344027701212726049781984643686711974001976\ 25023649303468776121253679423200058547956528088349 and 79258699544783330333470858414800596877379758573642\ 19960734330341455767872818152135381409304740185467 We did lattice sieving for most special q between 3e8 and 11e8 using mainly factor base bounds of 3e8 on the algebraic side and 18e7 on the rational side. The bounds for large primes were 2^35. This produced 26e8 relations. Together with 5e7 relations from line sieving the total yield was 27e8 relations. After removing duplicates 226e7 relations remained. A filter job produced a matrix with 64e6 rows and columns, having 11e9 non-zero entries. This was solved by Block-Wiedemann. Sieving has been done on a variety of machines. We estimate that lattice sieving would have taken 55 years on a single 2.2 GHz Opteron CPU. Note that this number could have been improved if instead of the PIII- binary which we used for sieving, we had used a version of the lattice-siever optimized for Opteron CPU's which we developed in the meantime. The matrix step was performed on a cluster of 80 2.2 GHz Opterons connected via a Gigabit network and took about 3 months. We started sieving shortly before Christmas 2003 and continued until October 2004. The matrix step began in December 2004. Line sieving was done by P. Montgomery and H. te Riele at the CWI, by F. Bahr and his family. More details will be given later. F. Bahr, M. Boehm, J. Franke, T. Kleinjung [private communication from 7 Sep 2008: the polynomial used had degree 5.] [below is the polynomial used, sent by Thorsten Kleinjung, 17 Feb 2009] 27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983 #skewness 2766778.76 norm 3.83e+27 alpha -6.76 Murphy_E 3.89e-15 X5 374029011720 X4 2711065637795630118 X3 19400071943177513865892714 X2 -33803470609202413094680462360399 X1 -120887311888241287002580512992469303610 X0 38767203000799321189782959529938771195170960 Y1 12722245648421103686881 Y0 -37570227807001155896638712233675454511 M 15240406298121496354551687149477757579964572007055177494848989490034525458250363151996418176514037886590177794384616498567367206741835552043570701523997401432185870335410144421338529115688465539646714 0 200000000 3.8 35 100 0 300B000000 3.7 35 100