73 digit ECM factor

[akruppa]

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

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 <champs@rpbrent.com>
(see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt)

Alex

[Batalov]

.......stammers........

Wow! Congrats to the monster team!!

[jrk]

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]

[ET_]

[ixfd64]

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!

[MatWur-S530113]

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?

[bdodson]

Originally Posted by jrk

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
near

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

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

[Andi47]

WOOOOW!!!

Congrats for this giant factor!!

[10metreh]

When I saw the thread title I thought it was a hoax.

[fivemack]

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.