ECM group order mystery

[Prime95]

Can anyone explain this:

Prime95 reports this:

ECM found a factor in curve #288, stage #2
Sigma=8055078829352661, B1=1000000, B2=2842011315.
UID: xxx, M257189 has a factor: 9076380491288497374472490688721 (ECM curve 288, B1=1000000, B2=2842011315)

Error message from factordb:
Err: Calculated grouporder 9076380491288499231237040277748<31> is not within B1/B2 bounds (B1=1000000, B2=2842011315). Please check your result!

factorization of the group order is (please notice the exceeded B1):
9076380491288499231237040277748<31> = 2^2 · 3^2 · 719 · 967 · 3613543 · 100350976151081387<18>

[axn]

Originally Posted by Prime95

Can anyone explain this:

Is the computation repeatable with the same sigma? Perhaps the sigma got corrupted -- either during printing or during computation?

FWIW, Pari agrees with factordb

ecmgroup(p, s)={
my(v,u,x,b,a,A,E);
s=Mod(s,p);
v=4*s;
u=s^2-5;
x=u^3;
b=4*x*v;
a=(v-u)^3*(3*u+v);
A=a/b-2;
x=x/v^3;
b=x^3+A*x^2+x;
E=ellinit([0,b*A,0,b^2,0]);
ellgroup(E)
}
p=9076380491288497374472490688721;
s=8055078829352661;
ecmgroup(p,s)
[9076380491288499231237040277748]

[frmky]

Assuming ecm -param 3 gives a group order of
9076380491288497514442256285656<31> = 2^3 · 3 · 13^2 · 9887 · 863843 · 262008508458197461<18>
That's within B1 but significantly exceeds B2.

[Prime95]

Originally Posted by axn

Is the computation repeatable with the same sigma?

I could not reproduce the computation. I'll ask user xxx to try.

Corruption of the sigma value is possible -- though it seems unlikely. Corruptions usually result in crashes or incorrect results -- this time a corruption occurred and a factor was still found. But, I have no other explanation.

[xilman]

Originally Posted by Prime95

I could not reproduce the computation. I'll ask user xxx to try.

Corruption of the sigma value is possible -- though it seems unlikely. Corruptions usually result in crashes or incorrect results -- this time a corruption occurred and a factor was still found. But, I have no other explanation.

I wouldn't spend too much effort investigating it myself. It is interesting, but as long as the factor is valid, who cares in the end?

[bbb120]

Originally Posted by Prime95

Can anyone explain this:

Prime95 reports this:

ECM found a factor in curve #288, stage #2
Sigma=8055078829352661, B1=1000000, B2=2842011315.
UID: xxx, M257189 has a factor: 9076380491288497374472490688721 (ECM curve 288, B1=1000000, B2=2842011315)

Error message from factordb:
Err: Calculated grouporder 9076380491288499231237040277748<31> is not within B1/B2 bounds (B1=1000000, B2=2842011315). Please check your result!

factorization of the group order is (please notice the exceeded B1):
9076380491288499231237040277748<31> = 2^2 · 3^2 · 719 · 967 · 3613543 · 100350976151081387<18>

why you cannot reproduce the computation since you have the sigma and B1 and B2?
and it is really very interesting (B2<<100350976151081387<18>)

[VBCurtis]

If we knew why, we wouldn't have a mystery now, would we?

[kruoli]

This has happened to me before and I also recall someone else mentioning it on the forum (starting from post #7). So this is not an one-off.

[Neptune]

Looking at the parameterization of the curve between line 3232 and 3305 in ecm.cpp (version 30.8b15):

u = sig² - 5
v = 4sig;
x = u³
z = v³
An = (v - u)³ (3u + v)
Ad4 = 4u³ v

seems all OK to me up to here, but for:

/* Normalize so that An is one */ <line 3283>
Ad4 = Ad4 ( (1 / An) % n)
Ad4 = 4Ad4

I'm not sure about.
Ad4 the former denominator now becomes the (normalized) numerator.

Suggestion:
Montgomery form requires A24 = (A + 2) / 4 (which can be of course precalculated).
As Suyama Parameterization already substracts A = A-2 in the last step we can ommit A-2 / A+2
and multiply the denomintaor Ad4 with four. Then one normalization in the last step to get the right parameterization:

u = sig² - 5
v = 4sig;
x = u³
z = v³
An = (v - u)³ (3u + v)

all as above but now:
Ad4 = 16u³ v
and
/* Normalize so that Ad4 is one */
Ad4 = An ( (1 / Ad4) % n)

That's all nothing more needs to be changed.

[axn]

Originally Posted by Prime95

Corruptions usually result in crashes or incorrect results -- this time a corruption occurred and a factor was still found.

Technically, finding a factor when it is not supposed to /is/ an incorrect result.

I just searched nearby values for sigmas that work. s+18 and s+2^168 (1-bit hamming distance) work. Of course it proves nothing. If we search enough sigmas, we'll get some that work.

[ATH]

GMP-ECM does not find it with that sigma:

ecm.exe -c 1 -v -savea M257189out.txt -maxmem 12000 -sigma 8055078829352661 1e6 2842011315 < M257189.txt
GMP-ECM 7.0.5-dev [configured with GMP 6.2.1, --enable-asm-redc] [ECM]
Input number is 2^257189-1 (77422 digits)
Using special division for factor of 2^257189-1
Using B1=1000000, B2=2842011315, polynomial Dickson(6), sigma=0:8055078829352661
dF=6720, k=6, d=66990, d2=13, i0=2
Expected number of curves to find a factor of n digits (assuming one exists):
35      40      45      50      55      60      65      70      75      80
749     6987    78397   1016542 1.5e+07 2.5e+08 4.8e+09 1.1e+11 8.5e+15 1.1e+21
Step 1 took 10437781ms
Estimated memory usage: 10.27GB
Initializing tables of differences for F took 26937ms
Computing roots of F took 247094ms
Building F from its roots took 338281ms
Computing 1/F took 99125ms
Initializing table of differences for G took 49281ms
Computing roots of G took 219203ms
Building G from its roots took 342281ms
Computing roots of G took 223500ms
Building G from its roots took 342797ms
Computing G * H took 65703ms
Reducing  G * H mod F took 106078ms
Computing roots of G took 224125ms
Building G from its roots took 341438ms
Computing G * H took 65344ms
Reducing  G * H mod F took 105906ms
Computing roots of G took 223250ms
Building G from its roots took 340969ms
Computing G * H took 65625ms
Reducing  G * H mod F took 105781ms
Computing roots of G took 222906ms
Building G from its roots took 341360ms
Computing G * H took 65469ms
Reducing  G * H mod F took 106062ms
Computing roots of G took 222500ms
Building G from its roots took 341406ms
Computing G * H took 65421ms
Reducing  G * H mod F took 105641ms
Computing polyeval(F,G) took 544062ms
Computing product of all F(g_i) took 18641ms
Step 2 took 5568125ms
Expected time to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
138.67d 3.55y   39.79y  515.94y 7648y   126232y 2e+06y  6e+07y  4e+12y  6e+17y
Peak memory usage: 7738MB