mersenneforum.org ECM group order mystery
 Register FAQ Search Today's Posts Mark Forums Read

 2022-09-20, 08:53 #12 Neptune   Jul 2022 3×7 Posts To enlighten the mystery a bit. The group order can be determined with Suyama's parametrization iff the factor was found in stage 1. go.gp Code: 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) }; Code: ================================================================================ 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] ================================================================================
 2022-09-21, 19:47 #13 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22·43·47 Posts 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.
 2022-09-21, 23:47 #14 WraithX     Mar 2006 10000011102 Posts 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.
 2022-09-22, 05:26 #15 ATH Einyen     Dec 2003 Denmark 3×17×67 Posts Is it only a problem in the new version 30.9 ECM or also older versions?
2022-09-22, 06:18   #16
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

11111100101002 Posts

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

2022-09-22, 15:56   #17
chris2be8

Sep 2009

3×11×73 Posts

Quote:
 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?

2022-09-22, 17:07   #18
axn

Jun 2003

34×67 Posts

Quote:
 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?

2022-09-22, 17:41   #19
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22·43·47 Posts

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

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

2022-09-22, 18:13   #20
ATH
Einyen

Dec 2003
Denmark

3·17·67 Posts

Quote:
 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?

2022-09-22, 19:53   #21
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

22×43×47 Posts

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

2022-09-22, 20:33   #22
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

808410 Posts

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

Last fiddled with by Prime95 on 2022-09-22 at 21:02

 Similar Threads Thread Thread Starter Forum Replies Last Post rwwh FactorDB 2 2015-06-19 06:26 Brain Miscellaneous Math 1 2010-12-08 01:00 wpolly Math 1 2008-06-09 12:14 gian92 Software 0 2008-02-22 21:08 ixfd64 Lounge 13 2007-03-23 15:06

All times are UTC. The time now is 08:06.

Fri Dec 9 08:06:23 UTC 2022 up 113 days, 5:34, 0 users, load averages: 0.82, 0.99, 1.09