mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

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

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
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts
Default

.......stammers........
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
 
jrk's Avatar
 
May 2008

3·5·73 Posts
Default

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

2×29×83 Posts
Default

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

2·3·397 Posts
Default

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
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2·34 Posts
Default

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
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by jrk View Post
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
bdodson is offline   Reply With Quote
Old 2010-03-07, 03:42   #8
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

23·32·5 Posts
Default

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
 
Andi47's Avatar
 
Oct 2004
Austria

248210 Posts
Default

WOOOOW!!!

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
 
10metreh's Avatar
 
Nov 2008

91216 Posts
Default



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
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

143578 Posts
Default

Quote:
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
Reply

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 00:11.

Wed May 12 00:11:43 UTC 2021 up 33 days, 18:52, 0 users, load averages: 4.01, 4.11, 3.85

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.