a p83 factor by ECM, the new champion

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

[R.D. Silverman]

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?

[bdodson]

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

[Batalov]

Surprisingly, the factordb.com knows the answer (simply click on "ECM" green arrow):

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.

[ryanp]

Hello,

Yes, I found this factor of 7^337+1 using GMP-ECM, not SNFS.

Here's the full log, for the curious:

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)

[sean]

Congratulations Ryan. That is a stunning result.

[R.D. Silverman]

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:

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?

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

[R.D. Silverman]

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.

[R.D. Silverman]

Originally Posted by sean

Congratulations Ryan. That is a stunning result.

An understatement.

[ryanp]

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. :)