ECM group order mystery

[Neptune]

The group order can be determined with Suyama's parametrization iff the factor was found in stage 1.


go.gp

go(p,sig) = {     /* group order with Suyama's parametrization */ 
  local(u, v, x, z, An, Ad, A, b, E);
  u = sig^2-5; 
  v = 4*sig;
  x = u^3;
  z = v^3;
  An = (v-u)^3*(3*u+v);
  Ad = 4*x*v;
  A = An/Ad-2;
  b = (x^3+A*x^2*z+x*z^2)/z;
  E = ellinit([0, b*A, 0, b^2, 0]);
  ellcard(E, p)
};

================================================================================
ECM on 6^16384+1: curve #223 with s=7941809365880582, B1=50000, B2=50000
6^16384+1 has a factor: 18220289247208144897 (ECM curve 223, B1=50000, B2=50000)

factor(go(p, sig))~
%1 = 
[2 3 17 523 719 1097 1153 23473]

[5 1  1   1   1    1    1     1]
================================================================================
ECM on M5113: curve #45 with s=3943578567805877, B1=50000, B2=50000
M5113 has a factor: 44652248830618077673 (ECM curve 45, B1=50000, B2=50000)

factor(go(p, sig))~
%2 = 
[2 3 13 1181 13691 27397 35897]

[3 3  1    1     1     1     1]
================================================================================
ECM on M8069: curve #28 with s=8417003857061369, B1=50000, B2=50000
M8069 has a factor: 3133683643066645087 (ECM curve 28, B1=50000, B2=50000)

factor(go(p, sig))~
%3 = 
[2 3 19 1201 4783 6869 29027]

[4 2  1    1    1    1     1]
================================================================================

[Prime95]

The bad sigma problem just happened to me, so it was not a one-time memory corruption -- it is a prime95 bug.

The most concerning thing is that the factor is not found by prime95 when rerun with the same sigma. It would be a minor problem if prime95 was computing curve starting parameters from a sigma value differently than GMP-ECM and other programs. I think it is a major problem that prime95 sometimes finds a factor with a given sigma and sometimes does not. Studying the code, I'm presently at a loss as to where the problem might be.

[WraithX]

Is there any way we can see the code for this new ecm functionality? Perhaps an extra pair of eyes, or a dozen!, can help find any potential issues.

[ATH]

Is it only a problem in the new version 30.9 ECM or also older versions?

[Prime95]

Originally Posted by ATH

Is it only a problem in the new version 30.9 ECM or also older versions?

Issue began in 30.6 -- affects stage 1 result. I have a painful way to find out which code change caused the problem.

[chris2be8]

Originally Posted by Prime95

The most concerning thing is that the factor is not found by prime95 when rerun with the same sigma.

Was it originally found after running several curves, then not found running one curve starting with the sigma reported for the curve that found it? That would suggest an uninitialised variable changed by a previous curve. This assumes it always fails when re-running.

Or is there any other pattern to when it works and when it does not? Does *always* work or not when run in *exactly* the same way?

[axn]

Originally Posted by Prime95

Issue began in 30.6 -- affects stage 1 result. I have a painful way to find out which code change caused the problem.

Is a fix forthcoming? Should I stop running ECM using 30.9 till then?

[Prime95]

Originally Posted by chris2be8

Was it originally found after running several curves, then not found running one curve starting with the sigma reported for the curve that found it? That would suggest an uninitialised variable changed by a previous curve. This assumes it always fails when re-running.

Or is there any other pattern to when it works and when it does not? Does *always* work or not when run in *exactly* the same way?

In my case, the factor was found on the 4th curve. The screen output shows the sigma value at start of the ECM run and when the factor was found. The variable holding the sigma value was not corrupted.

I've only tried rerunning the found factor twice. It failed to find the factor both times. I cannot yet explain how this could happen -- you're right it smells like some kind of improperly initialized variable.

Originally Posted by axn

Is a fix forthcoming? Should I stop running ECM using 30.9 till then?

A fix will be forthcoming once I find the bug. It seems the bug (or bugs) is not crippling ECM as I've found new factors with 30.9 (and it passed a dozen or two QA tests on known factors with known sigmas). The bug may be affecting the rate at which ECM finds factors -- I cannot say if the better stage 2 would more than compensate.

The person that reported the original problem came up with the breakthrough to finding the bug. He used GmpECMHook=1 to dump the output of ECM stage 1. He found that version 29.1 and 30.9 produced different results. I've narrowed the change down to versions 30.5 and 30.6. Now I have to go through source control and apply changes one by one to find the exact change that caused the difference.

[ATH]

Originally Posted by Prime95

In my case, the factor was found on the 4th curve. The screen output shows the sigma value at start of the ECM run and when the factor was found. The variable holding the sigma value was not corrupted.

Do you have the entire log? Did you try run all 4 curves again using the same 4 different sigmas?

[Prime95]

Originally Posted by Prime95

The person that reported the original problem came up with the breakthrough to finding the bug. He used GmpECMHook=1 to dump the output of ECM stage 1. He found that version 29.1 and 30.9 produced different results. I've narrowed the change down to versions 30.5 and 30.6. Now I have to go through source control and apply changes one by one to find the exact change that caused the difference.

Grrrr... false lead. A change in 30.6 caused an extra power-of-two to be include in stage 1. That's pretty harmless.

[Prime95]

Originally Posted by Prime95

Grrrr... false lead.

I've created a special version that always dumps the stage 1 result. I'm searching again for new factors in hopes the problem comes up again. At least then I'll be able to tell if the problem is from stage 1 or stage 2.

My best guess is some kind of multi-threading bug in stage 2 (hence non-reproducible) where the bad result luckily stumbles upon a factor. Though, that seems almost unbelievably lucky.


----
Edit: Even better, I now dump stage 1 and stage 2 result. I'll run several curves and then rerun them again withe same sigmas and compare results.