20050516, 20:57  #1 
Aug 2004
New Zealand
3^{2}·5^{2} Posts 
C151 118!+1 by GNFS finished
Today I completed the factorization of the C151 cofactor of 118!+1 by
GNFS. Total calendar time for this factorization was 49 days. 118!+1 = 46757 * 82219 * 1871263 * 11294645177647665140920980967 (Andrew Walker, 1998) * 26722464573695888110450933578985133184055013159596413387712641189727401257 * 215755998310817447135361660925170571172035520281882810599201805043440117717351 For this factorization I used the implementation of Franke, Kleinjung, and Bahr. Polynomial selection was by Kleinjung's method. Thanks also to Jes Hansen for scripts which made this task easier. BEGIN POLY #skewness 221289.42 norm 8.93e+20 alpha 6.67 Murphy_E 4.66e12 X5 72496440 X4 8531351692062 X3 16095568481020701977 X2 237475459914786872640202 X1 66015102678891792487030736008 X0 8378573736183516069721926682785600 Y1 370663252551053891 Y0 38028101219232514145714792201 I did lattice sieving for all special q between 20e6 and 93.3e6 using factor base bounds of 16e6 on the algebraic side and 10e6 on the rational side. The bounds for large primes were 2^32. Sieving ran for just under a month from 20050329 to 20050426 on a range of machines. After filtering the matrix was 5096931 * 5097029 which just squeezed into 2GB RAM. My first attempt to reduce the matrix failed when my harddrive died (fortunately the factor data was on another disk). The second run started on 20050427 and completed on 20050515. The factor was found on the third dependency. Originally I thought this would put me safely in the top 10; but the other two really big factorizations this month have seen this result squeezed precariously to tenth or maybe out of the top 10 altogether if I am missing other recent results. RSA200 2005 2799 C200=P100*P100 GNFS Bahr/Franke/Kleinjung/et al. 11^281+1 2005 1009 C176=P87*P89 GNFS Aoki, Kida, Shimoyama, Ueda RSA576 2003 1881 C174=P87*P87 GNFS Bahr/Franke/Kleinjung/Montgomery/te Riele/Leclair/Leyland/Wackerbarth 2^1826+1 2003 9758 C164=P68*P97 GNFS Aoki, Kida, Shimoyama, Sonoda, Ueda RSA160 2003 2152 C160=P80*P80 GNFS Bahr/Franke/Kleinjung/Lochter/Bohm 2^953+1 2002 3950 C158=P73*P86 GNFS Bahr/Franke/Kleinjung RSA155 1999 1094 C155=P78*P78 GNFS te Riele/CWI et al. Code Book 2000 1074 C155=P78*P78 GNFS Almgren/Andersson/Granlund/Ivansson/Ulfberg HP49(95) 2003 2651 C153=P68*P85 GNFS Kruppa/Leyland 118!+1 2005 5765 C151=P74*P78 GNFS Irvine HP49(97) 2003 1268 C151=P55*P96 GNFS Kruppa/Leyland For more information on the n!1 and n!+1 factoring project see http://www.uow.edu.au/%7Eajw01/ecm/curves.html Sean Irvine 
20050517, 01:06  #2  
Mar 2003
1001110_{2} Posts 
Quote:
Out of curiosity, how many machines (and of what average processing power) did you use for the sieving and for the linear algebra? In case you are interested in a significantly smaller but comparable benchmark I finished a 3.30M matrix not too long ago on an Athlon XP 2500+ in 15 days using the CWI suite. Don Leclair 

20050517, 01:33  #3 
Aug 2004
New Zealand
3^{2}×5^{2} Posts 
The matrix reduction was done on a 2.8 GHz Pentium 4 with 2GB of RAM
(which happens to be my desktop machine, so had to share this with X etc.) It is harder for my to characterize the CPU power available for sieving. The specs of the machines used for sieving are as follows but these machines are shared for our real work. I guess I averaged about 10 GHz over the time sieving occurred. 2 * 800 MHz PIII 2 * 866 MHz PIII 2 * 2.8 GHz PIV 1 * 3.2 GHz PIV 1 * 1.6 GHz Athlon In my experience the Franke lanczos implementation is faster than CWI on Pentium machines and perhaps Athlons as well. 
20050517, 03:40  #4 
Oct 2004
tropical Massachusetts
3·23 Posts 
Congratulations on this achievement. Just 11 bits longer and it could have been a 512bit RSA key. It amazes me that something like this can be done with 8 or 9 commodity machines now.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
137!+1 C159 finished by GNFS  sean  Factoring  11  20060324 01:22 
The factorization of 6,257+.c151  xilman  NFSNET Discussion  1  20041014 13:29 
37M finished to 60 bit  hbock  Lone Mersenne Hunters  0  20040721 20:30 
25.48M to 25.5M up to 2^58 finished  Thomas11  Lone Mersenne Hunters  0  20030305 18:57 
25.5M to 26M up to 2^58 finished  Thomas11  Lone Mersenne Hunters  5  20030304 09:55 