mersenneforum.org a p83 factor by ECM, the new champion
 Register FAQ Search Today's Posts Mark Forums Read

 2013-09-08, 13:28 #1 R.D. Silverman     Nov 2003 164448 Posts a p83 factor by ECM, the new champion Sam just reported that Ryan found a p83 factor of 7,337+ by ECM !!!!! This is truly awesome. Unless, of course, it was really done by SNFS and Sam just made a mistake.........
2013-09-08, 13:32   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by R.D. Silverman Sam just reported that Ryan found a p83 factor of 7,337+ by ECM !!!!! This is truly awesome. Unless, of course, it was really done by SNFS and Sam just made a mistake.........
It's been 3 weeks since Ryan's last SNFS result. It is possible that he
has been running ECM all this time...... It would be nice to know
what is really happening. i.e. What numbers has Ryan attempted with ECM
and what limits he is using, as well as how many curves he is running......

Has he put the NFS work on hold? The world wonders.

Does anyone have his email address?

2013-09-08, 16:30   #3
bdodson

Jun 2005
lehigh.edu

40016 Posts
believable?

Quote:
 Originally Posted by R.D. Silverman Sam just reported that Ryan found a p83 factor of 7,337+ by ECM !!!!! This is truly awesome. Unless, of course, it was really done by SNFS and Sam just made a mistake.........
Well. Three ECM factors from 2^N-1, 1000 < N <1200 left by
epfl's t65 is almost equally unlikely; at C256, C248 and C260,
uhm, that's N < 1070 ... more likely to have been SNFS than GNFS.

As a candidate for Ryan to run ecm-testing, this is a first hole;
promoted when he did 7,334+ by snfs.

If/when it's confirmed and sent to PaulZ, this would be an effective
way to bump p69's off of the Top10 ...

-Bruce

 2013-09-08, 18:32 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×13×359 Posts Surprisingly, the factordb.com knows the answer (simply click on "ECM" green arrow): Code: Factor 16559819925107279963180573885975861071762981898238616724384425798932514688349020287 This factor was found by ECM B1 7600000000 B2 324909696561468 Sigma 3882127693 Report date September 7, 2013, 8:45 pm Reported by Ryan P. Group order 16559819925107279963180573885975861071762950363704499914109215737790822658380702832 = 2^4 · 3^2 · 11 · 37 · 47 · 71 · 701 · 8089 · 8867 · 369959 · 418837 · 1652033 · 7073741 · 306305009 · 338404169 · 1143896321 · 7843501130401 To paraphrase Sam's report: "Another mathematical feat accomplished years ahead of expectations." P.S. I have filled it in the PaulZ's report form. Feast your eyes at this. Last fiddled with by Batalov on 2013-09-08 at 18:37
 2013-09-08, 19:26 #5 ryanp     Jun 2012 Boulder, CO 4128 Posts Hello, Yes, I found this factor of 7^337+1 using GMP-ECM, not SNFS. Here's the full log, for the curious: Code: GMP-ECM 6.4.3 [configured with GMP 5.1.0, --enable-asm-redc] [ECM] Input number is 777215638724902495611175360343574282841920454031590769938320008426822296294887796237499712622482604214003616693892758604051211598461971146444570844827214880797476620823624217986021918983892640734704548229570263847528864389309127527373789 (237 digits) Using MODMULN [mulredc:0, sqrredc:1] Using B1=7600000000, B2=324909696561468, polynomial Dickson(30), sigma=3882127693 dF=1048576, k=25, d=11741730, d2=19, i0=629 Expected number of curves to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 8 21 60 190 660 2483 9979 42978 194971 938688 Step 1 took 43851609ms Using 28 small primes for NTT Estimated memory usage: 5529M Initializing tables of differences for F took 5612ms Computing roots of F took 147548ms Building F from its roots took 89207ms Computing 1/F took 33622ms Initializing table of differences for G took 1450ms Computing roots of G took 121388ms Building G from its roots took 97552ms Computing roots of G took 122161ms Building G from its roots took 96634ms Computing G * H took 17265ms Reducing G * H mod F took 17752ms Computing roots of G took 122015ms Building G from its roots took 97421ms Computing G * H took 17628ms Reducing G * H mod F took 17812ms Computing roots of G took 121397ms Building G from its roots took 96206ms Computing G * H took 17564ms Reducing G * H mod F took 17806ms Computing roots of G took 122015ms Building G from its roots took 96276ms Computing G * H took 17464ms Reducing G * H mod F took 17822ms Computing roots of G took 122069ms Building G from its roots took 96125ms Computing G * H took 17290ms Reducing G * H mod F took 17809ms Computing roots of G took 122824ms Building G from its roots took 108395ms Computing G * H took 20035ms Reducing G * H mod F took 20256ms Computing roots of G took 140490ms Building G from its roots took 108015ms Computing G * H took 19103ms Reducing G * H mod F took 19300ms Computing roots of G took 135875ms Building G from its roots took 114475ms Computing G * H took 20014ms Reducing G * H mod F took 19630ms Computing roots of G took 135408ms Building G from its roots took 95380ms Computing G * H took 16593ms Reducing G * H mod F took 16669ms Computing roots of G took 114518ms Building G from its roots took 92394ms Computing G * H took 16887ms Reducing G * H mod F took 17464ms Computing roots of G took 116052ms Building G from its roots took 91016ms Computing G * H took 16608ms Reducing G * H mod F took 16970ms Computing roots of G took 115721ms Building G from its roots took 92274ms Computing G * H took 16995ms Reducing G * H mod F took 17087ms Computing roots of G took 116874ms Building G from its roots took 91876ms Computing G * H took 17051ms Reducing G * H mod F took 16940ms Computing roots of G took 116820ms Building G from its roots took 93460ms Computing G * H took 16890ms Reducing G * H mod F took 16768ms Computing roots of G took 116331ms Building G from its roots took 92185ms Computing G * H took 16621ms Reducing G * H mod F took 16806ms Computing roots of G took 116494ms Building G from its roots took 92963ms Computing G * H took 16708ms Reducing G * H mod F took 17283ms Computing roots of G took 116918ms Building G from its roots took 91781ms Computing G * H took 16473ms Reducing G * H mod F took 16791ms Computing roots of G took 117170ms Building G from its roots took 92927ms Computing G * H took 17218ms Reducing G * H mod F took 16878ms Computing roots of G took 114498ms Building G from its roots took 91172ms Computing G * H took 16601ms Reducing G * H mod F took 16862ms Computing roots of G took 114789ms Building G from its roots took 92090ms Computing G * H took 16650ms Reducing G * H mod F took 16894ms Computing roots of G took 115192ms Building G from its roots took 91777ms Computing G * H took 16684ms Reducing G * H mod F took 17003ms Computing roots of G took 115149ms Building G from its roots took 91201ms Computing G * H took 16646ms Reducing G * H mod F took 16809ms Computing roots of G took 115024ms Building G from its roots took 91064ms Computing G * H took 16684ms Reducing G * H mod F took 16941ms Computing roots of G took 115807ms Building G from its roots took 89897ms Computing G * H took 16386ms Reducing G * H mod F took 16574ms Computing polyeval(F,G) took 157074ms Computing product of all F(g_i) took 642ms Step 2 took 6663183ms ********** Factor found in step 2: 16559819925107279963180573885975861071762981898238616724384425798932514688349020287 Found probable prime factor of 83 digits: 16559819925107279963180573885975861071762981898238616724384425798932514688349020287 Probable prime cofactor 46933821879700629469737272143825424094692046402362130628425060311116168813673425035556321945601230435566363580819053175608838465629867780302484884127126947 has 155 digits Report your potential champion to Richard Brent (see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt)
 2013-09-08, 19:56 #6 sean     Aug 2004 New Zealand 22210 Posts Congratulations Ryan. That is a stunning result.
2013-09-08, 20:15   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by ryanp Hello, Yes, I found this factor of 7^337+1 using GMP-ECM, not SNFS. Here's the full log, for the curious: Code: GMP-ECM 6.4.3 [configured with GMP 5.1.0, --enable-asm-redc] [ECM] Input number is 777215638724902495611175360343574282841920454031590769938320008426822296294887796237499712622482604214003616693892758604051211598461971146444570844827214880797476620823624217986021918983892640734704548229570263847528864389309127527373789 (237 digits) Using MODMULN [mulredc:0, sqrredc:1] Using B1=7600000000, B2=324909696561468, polynomial Dickson(30), sigma=3882127693 dF=1048576, k=25, d=11741730, d2=19, i0=629 Expected number of curves to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 8 21 60 190 660 2483 9979 42978 194971 938688 Step 1 took 43851609ms Using 28 small primes for NTT Estimated memory usage: 5529M Initializing tables of differences for F took 5612ms Computing roots of F took 147548ms Building F from its roots took 89207ms Computing 1/F took 33622ms Initializing table of differences for G took 1450ms Computing roots of G took 121388ms Building G from its roots took 97552ms Computing roots of G took 122161ms Building G from its roots took 96634ms Computing G * H took 17265ms Reducing G * H mod F took 17752ms Computing roots of G took 122015ms Building G from its roots took 97421ms Computing G * H took 17628ms Reducing G * H mod F took 17812ms Computing roots of G took 121397ms Building G from its roots took 96206ms Computing G * H took 17564ms Reducing G * H mod F took 17806ms Computing roots of G took 122015ms Building G from its roots took 96276ms Computing G * H took 17464ms Reducing G * H mod F took 17822ms Computing roots of G took 122069ms Building G from its roots took 96125ms Computing G * H took 17290ms Reducing G * H mod F took 17809ms Computing roots of G took 122824ms Building G from its roots took 108395ms Computing G * H took 20035ms Reducing G * H mod F took 20256ms Computing roots of G took 140490ms Building G from its roots took 108015ms Computing G * H took 19103ms Reducing G * H mod F took 19300ms Computing roots of G took 135875ms Building G from its roots took 114475ms Computing G * H took 20014ms Reducing G * H mod F took 19630ms Computing roots of G took 135408ms Building G from its roots took 95380ms Computing G * H took 16593ms Reducing G * H mod F took 16669ms Computing roots of G took 114518ms Building G from its roots took 92394ms Computing G * H took 16887ms Reducing G * H mod F took 17464ms Computing roots of G took 116052ms Building G from its roots took 91016ms Computing G * H took 16608ms Reducing G * H mod F took 16970ms Computing roots of G took 115721ms Building G from its roots took 92274ms Computing G * H took 16995ms Reducing G * H mod F took 17087ms Computing roots of G took 116874ms Building G from its roots took 91876ms Computing G * H took 17051ms Reducing G * H mod F took 16940ms Computing roots of G took 116820ms Building G from its roots took 93460ms Computing G * H took 16890ms Reducing G * H mod F took 16768ms Computing roots of G took 116331ms Building G from its roots took 92185ms Computing G * H took 16621ms Reducing G * H mod F took 16806ms Computing roots of G took 116494ms Building G from its roots took 92963ms Computing G * H took 16708ms Reducing G * H mod F took 17283ms Computing roots of G took 116918ms Building G from its roots took 91781ms Computing G * H took 16473ms Reducing G * H mod F took 16791ms Computing roots of G took 117170ms Building G from its roots took 92927ms Computing G * H took 17218ms Reducing G * H mod F took 16878ms Computing roots of G took 114498ms Building G from its roots took 91172ms Computing G * H took 16601ms Reducing G * H mod F took 16862ms Computing roots of G took 114789ms Building G from its roots took 92090ms Computing G * H took 16650ms Reducing G * H mod F took 16894ms Computing roots of G took 115192ms Building G from its roots took 91777ms Computing G * H took 16684ms Reducing G * H mod F took 17003ms Computing roots of G took 115149ms Building G from its roots took 91201ms Computing G * H took 16646ms Reducing G * H mod F took 16809ms Computing roots of G took 115024ms Building G from its roots took 91064ms Computing G * H took 16684ms Reducing G * H mod F took 16941ms Computing roots of G took 115807ms Building G from its roots took 89897ms Computing G * H took 16386ms Reducing G * H mod F took 16574ms Computing polyeval(F,G) took 157074ms Computing product of all F(g_i) took 642ms Step 2 took 6663183ms ********** Factor found in step 2: 16559819925107279963180573885975861071762981898238616724384425798932514688349020287 Found probable prime factor of 83 digits: 16559819925107279963180573885975861071762981898238616724384425798932514688349020287 Probable prime cofactor 46933821879700629469737272143825424094692046402362130628425060311116168813673425035556321945601230435566363580819053175608838465629867780302484884127126947 has 155 digits Report your potential champion to Richard Brent (see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt)
How many curves were run?

What other numbers have been tried?

Have you stopped your NFS work?

 2013-09-08, 22:07 #8 PBMcL     Jan 2005 2·31 Posts Ryan should go buy a lottery ticket NOW! Note from the report that with the parameters chosen, this one curve took a bit over 14 hours to complete, and the expected number of curves to find a p83 (with probability 0.5?) is on the order of one million.
2013-09-08, 22:28   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by PBMcL Note from the report that with the parameters chosen, this one curve took a bit over 14 hours to complete, and the expected number of curves to find a p83 (with probability 0.5?) is on the order of one million.
You get the NSS award. Thanks for telling us what was obvious.
The question of how many curves were actually run is, of course,
still open.

2013-09-08, 22:33   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by sean Congratulations Ryan. That is a stunning result.
An understatement.

 2013-09-09, 00:31 #11 ryanp     Jun 2012 Boulder, CO 2×7×19 Posts For this job, I did about 5,000 curves, spanning about 10 days, on the FarmShare compute cluster at Stanford. I guess this was quite the lucky find. :)

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 FermatSearch 2 2018-01-24 04:35 TheMawn Lounge 0 2014-04-11 02:41 penguinman007 Factoring 4 2005-08-21 11:19 Ivan Semenov Data 2 2004-05-29 14:30 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 11:58.

Tue Mar 9 11:58:41 UTC 2021 up 96 days, 8:09, 0 users, load averages: 1.03, 1.38, 1.39