mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-09-08, 13:28   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default 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.........
R.D. Silverman is offline   Reply With Quote
Old 2013-09-08, 13:32   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2013-09-08, 16:30   #3
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

40016 Posts
Default believable?

Quote:
Originally Posted by R.D. Silverman View Post
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
bdodson is offline   Reply With Quote
Old 2013-09-08, 18:32   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×13×359 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2013-09-08, 19:26   #5
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

4128 Posts
Default

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 <champs@rpbrent.com>
(see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt)
ryanp is offline   Reply With Quote
Old 2013-09-08, 19:56   #6
sean
 
sean's Avatar
 
Aug 2004
New Zealand

22210 Posts
Default

Congratulations Ryan. That is a stunning result.
sean is offline   Reply With Quote
Old 2013-09-08, 20:15   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by ryanp View Post
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 <champs@rpbrent.com>
(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?
R.D. Silverman is offline   Reply With Quote
Old 2013-09-08, 22:07   #8
PBMcL
 
PBMcL's Avatar
 
Jan 2005

2·31 Posts
Default 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.
PBMcL is offline   Reply With Quote
Old 2013-09-08, 22:28   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by PBMcL View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-09-08, 22:33   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by sean View Post
Congratulations Ryan. That is a stunning result.
An understatement.
R.D. Silverman is offline   Reply With Quote
Old 2013-09-09, 00:31   #11
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

2×7×19 Posts
Default

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. :)
ryanp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new factor of F11?! siegert81 FermatSearch 2 2018-01-24 04:35
Fun factor TheMawn Lounge 0 2014-04-11 02:41
Factor me this penguinman007 Factoring 4 2005-08-21 11:19
use of factor? (just to be sure) Ivan Semenov Data 2 2004-05-29 14:30
Shortest time to complete a 2^67 trial factor (no factor) 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

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.