mersenneforum.org C151 118!+1 by GNFS finished
 Register FAQ Search Today's Posts Mark Forums Read

 2005-05-16, 20:57 #1 sean     Aug 2004 New Zealand 32·52 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.66e-12 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 2005-03-29 to 2005-04-26 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 hard-drive died (fortunately the factor data was on another disk). The second run started on 2005-04-27 and completed on 2005-05-15. 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. RSA-200 2005 2799 C200=P100*P100 GNFS Bahr/Franke/Kleinjung/et al. 11^281+1 2005 1009 C176=P87*P89 GNFS Aoki, Kida, Shimoyama, Ueda RSA-576 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 RSA-160 2003 2152 C160=P80*P80 GNFS Bahr/Franke/Kleinjung/Lochter/Bohm 2^953+1 2002 3950 C158=P73*P86 GNFS Bahr/Franke/Kleinjung RSA-155 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
2005-05-17, 01:06   #2
dleclair

Mar 2003

10011102 Posts

Quote:
 Today I completed the factorization of the C151 cofactor of 118!+1 by GNFS. Total calendar time for this factorization was 49 days.
Very impressive, congratulations!

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

 2005-05-17, 01:33 #3 sean     Aug 2004 New Zealand 32×52 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 P-III 2 * 866 MHz P-III 2 * 2.8 GHz P-IV 1 * 3.2 GHz P-IV 1 * 1.6 GHz Athlon In my experience the Franke lanczos implementation is faster than CWI on Pentium machines and perhaps Athlons as well.
 2005-05-17, 03:40 #4 trilliwig     Oct 2004 tropical Massachusetts 3·23 Posts Congratulations on this achievement. Just 11 bits longer and it could have been a 512-bit RSA key. It amazes me that something like this can be done with 8 or 9 commodity machines now.

 Similar Threads Thread Thread Starter Forum Replies Last Post sean Factoring 11 2006-03-24 01:22 xilman NFSNET Discussion 1 2004-10-14 13:29 hbock Lone Mersenne Hunters 0 2004-07-21 20:30 Thomas11 Lone Mersenne Hunters 0 2003-03-05 18:57 Thomas11 Lone Mersenne Hunters 5 2003-03-04 09:55

All times are UTC. The time now is 20:33.

Tue Jan 18 20:33:03 UTC 2022 up 179 days, 15:02, 0 users, load averages: 2.18, 1.74, 1.52