Go Back > Factoring Projects > Factoring

Thread Tools
Old 2010-03-06, 22:11   #1
akruppa's Avatar
Aug 2002

246710 Posts
Default 73 digit ECM factor

Originally Posted by Thorsten Kleinjung
Dear all,

we (Joppe Bos, Thorsten Kleinjung, Arjen Lenstra, Peter Montgomery)
found the following 73-digit prime factor
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,

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 <>

Last fiddled with by akruppa on 2010-03-06 at 22:17
akruppa is offline   Reply With Quote
Old 2010-03-06, 22:14   #2
Batalov's Avatar
Mar 2008

2×5×23×41 Posts

Name:  jawdrop.gif
Views: 1863
Size:  2.4 KB
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)
Batalov is offline   Reply With Quote
Old 2010-03-06, 22:23   #3
jrk's Avatar
May 2008

3·5·73 Posts

Group order is:

[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]
jrk is offline   Reply With Quote
Old 2010-03-06, 23:31   #4
ET_'s Avatar
Aug 2002
Team Italia

2×29×83 Posts

ET_ is offline   Reply With Quote
Old 2010-03-06, 23:46   #5
Bemusing Prompter
ixfd64's Avatar
Dec 2002

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
ixfd64 is offline   Reply With Quote
Old 2010-03-07, 00:20   #6
MatWur-S530113's Avatar
Apr 2007

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?
MatWur-S530113 is offline   Reply With Quote
Old 2010-03-07, 01:32   #7
bdodson's Avatar
Jun 2005

210 Posts

Originally Posted by jrk View Post
Group order is:

[1923401731 1]

[10801302048203 1]
As long as we're recording "wow's", take a look at the step1 prime,
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
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
bdodson is offline   Reply With Quote
Old 2010-03-07, 03:42   #8
FactorEyes's Avatar
Oct 2006

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.
FactorEyes is offline   Reply With Quote
Old 2010-03-07, 05:59   #9
Andi47's Avatar
Oct 2004

2·17·73 Posts


Congrats for this giant factor!!

Last fiddled with by Andi47 on 2010-03-07 at 06:06
Andi47 is offline   Reply With Quote
Old 2010-03-07, 07:33   #10
10metreh's Avatar
Nov 2008

2·33·43 Posts

When I saw the thread title I thought it was a hoax.
10metreh is offline   Reply With Quote
Old 2010-03-07, 10:17   #11
(loop (#_fork))
fivemack's Avatar
Feb 2006
Cambridge, England

638410 Posts

Originally Posted by FactorEyes View Post
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.
fivemack is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Factor a 108-digit number sweety439 Factoring 9 2016-12-21 21:22
New 70 digit factor R.D. Silverman Cunningham Tables 16 2016-01-23 22:16
44-digit factor found using ECM w/ B1=1e6 & B2=1e8 WVU Mersenneer Factoring 8 2010-04-24 17:01
Probability of n-digit factor? roger Factoring 3 2007-05-09 22:51
160 digit factor found of 366 digit (PRP-1) 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.