mersenneforum.org 73 digit ECM factor
 Register FAQ Search Today's Posts Mark Forums Read

2010-03-06, 22:11   #1
akruppa

"Nancy"
Aug 2002
Alexandria

246710 Posts
73 digit ECM factor

Quote:
 Originally Posted by Thorsten Kleinjung Dear all, we (Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, Peter Montgomery) found the following 73-digit prime factor 1808422353177349564546512035512530001279481259854248860454348989451026887 of 2^1181-1 by ECM, completing the factorisation of this number. Some details of this computation: We used Paul Zimmermann's GMP-ECM program with some modifications: Stage 1: we implemented arithmetic functions for Playstation3s for Mersenne numbers. Stage 1 for 24 curves in parallel and for B1=3*10^9 took less than 23 hours on one PS3, i.e., less than one hour per curve per PS3. Stage 2: we parallelised some functions, this stage with the default value of B2 of about 10^14 took about 15 minutes on 4 cores (per curve). We ran more than 30000 stage 1 and 8800 stage 2 computations. See below for the output of the lucky job. This is a nice factor at ECM's 25th anniversary. Best regards, Thorsten Code: GMP-ECM 6.2.3 [powered by GMP 4.3.1] [ECM] Resuming ECM residue saved by jwbos@node-3-6.ps3 with GMP-ECM 5.0 on Wed Mar 3 14:03:04 2010 Input number is 176185533608779112426057212156915737261973725692777098729042794211002730969474260553528629693362630813445982221616581896014560600230501525946408962727837512415610132135965435178668094176985071980937279402238467438168204332393198436347681167033274334629858331628089772185868567968860006604487 (291 digits) Using B1=3000000000-3000000000, B2=103971375307818, polynomial x^1, sigma=4000027779 Step 1 took 0ms Step 2********** Factor found in step 2: 1808422353177349564546512035512530001279481259854248860454348989451026887 Found probable prime factor of 73 digits: 1808422353177349564546512035512530001279481259854248860454348989451026887 Probable prime cofactor 97424992175763507877707709291914998778015966147054584755896881783255837016412999374281145264013986049748696515423136622647352488174403160324612550620242636441380838851457881913863524385273540967010429382172447745964801 has 218 digits Report your potential champion to Richard Brent (see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt)
Alex

Last fiddled with by akruppa on 2010-03-06 at 22:17

 2010-03-06, 22:14 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×5×23×41 Posts .......stammers........ Wow! Congrats to the monster team!! Last fiddled with by Batalov on 2010-03-06 at 22:19 Reason: (no hamsters were harmed with this image)
 2010-03-06, 22:23 #3 jrk     May 2008 3·5·73 Posts Group order is: Code: [2 4] [3 2] [13 1] [23 1] [61 1] [379 1] [13477 1] [272603 1] [12331747 1] [19481797 1] [125550349 1] [789142847 1] [1923401731 1] [10801302048203 1]
 2010-03-06, 23:31 #4 ET_ Banned     "Luigi" Aug 2002 Team Italia 2×29×83 Posts
 2010-03-06, 23:46 #5 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 45168 Posts Wow, this is an incredible milestone. According to Paul Zimmerman's website, this new divisor broke the previous ECM factoring record by five digits. Maybe you guys will discover a new Mersenne prime soon as well! Last fiddled with by ixfd64 on 2010-03-06 at 23:53 Reason: reword
 2010-03-07, 00:20 #6 MatWur-S530113     Apr 2007 Spessart/Germany 16210 Posts omg, congratulations to the team! I think we need to buy some PS3... one hour for one stage 1 with B1=3e9... With ECM 2005 the first 6x-digit factor was found (afaik), now 2010 the first factor with 7x digit. When the first 8x will be found?
2010-03-07, 01:32   #7
bdodson

Jun 2005
lehigh.edu

210 Posts

Quote:
 Originally Posted by jrk Group order is: Code:  ... [1923401731 1] [10801302048203 1]
As long as we're recording "wow's", take a look at the step1 prime,
Code:
1923401731 = step1 prime
3000000000 = B1
So B1 = 1900000000 = 1.9e9 would have missed. Likewise, step2.
Small memory might have used B2 = 100*B1 = 300e9, but that's nowhere
near
Code:
10801302048203 step2 prime
= 1.08e13
< 103971375307818 = 1.04e14 = B2
the default gmp-ecm step2. That's 8800 of these; wonder what the
memory needed for this step 2 was?

So mostly all of the step 1 bound was needed, and only a factor of
10 below the max possible step2, way far past low-moderate memory
use. I'm presuming that epfl isn't entirely satisfied. Arjen has a
test-case RSA key consisting of a product of four 256-bit primes
(none of this pq stuff, if no one's able to find 70-digit prime factors).
That's somewhere up in 77-digits, decimal, and this 73-digit prime
seems to have taken all that the ps3 1st step/heavy_memory_gmp-ecm_2nd
has. -Bruce

PS -- I've posted a link to Arjen's Gif of the ps3s over in the 2- subthread at
http://www.mersenneforum.org/showthr...425#post207425

 2010-03-07, 03:42 #8 FactorEyes     Oct 2006 vomit_frame_pointer 23×32×5 Posts I guess we can kiss off any dreams of having the #1 ECM hit this year. All the p68 through p72 factors I have found are now ECM misses.
 2010-03-07, 05:59 #9 Andi47     Oct 2004 Austria 2·17·73 Posts WOOOOW!!! Congrats for this giant factor!! Last fiddled with by Andi47 on 2010-03-07 at 06:06
 2010-03-07, 07:33 #10 10metreh     Nov 2008 2·33·43 Posts When I saw the thread title I thought it was a hoax.
2010-03-07, 10:17   #11
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

638410 Posts

Quote:
 Originally Posted by FactorEyes I guess we can kiss off any dreams of having the #1 ECM hit this year. All the p68 through p72 factors I have found are now ECM misses.
Not unless you've been pulling them out of thousand-bit hard SNFS numbers, which you haven't by definition of 'hard'; doing ECM for longer than it would take to factor the number by SNFS is a definition of stupidity.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 Factoring 9 2016-12-21 21:22 R.D. Silverman Cunningham Tables 16 2016-01-23 22:16 WVU Mersenneer Factoring 8 2010-04-24 17:01 roger Factoring 3 2007-05-09 22:51 AntonVrba Factoring 7 2005-12-06 22:02

All times are UTC. The time now is 06:05.

Thu May 13 06:05:20 UTC 2021 up 35 days, 46 mins, 0 users, load averages: 1.96, 1.90, 2.09