mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2022-09-20, 08:53   #12
Neptune
 
Jul 2022

3×7 Posts
Default 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]
================================================================================
Neptune is offline   Reply With Quote
Old 2022-09-21, 19:47   #13
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22×43×47 Posts
Default

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.
Prime95 is offline   Reply With Quote
Old 2022-09-21, 23:47   #14
WraithX
 
WraithX's Avatar
 
Mar 2006

52610 Posts
Default

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.
WraithX is offline   Reply With Quote
Old 2022-09-22, 05:26   #15
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,413 Posts
Default

Is it only a problem in the new version 30.9 ECM or also older versions?
ATH is online now   Reply With Quote
Old 2022-09-22, 06:18   #16
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22×43×47 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
Prime95 is offline   Reply With Quote
Old 2022-09-22, 15:56   #17
chris2be8
 
chris2be8's Avatar
 
Sep 2009

29×83 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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?
chris2be8 is offline   Reply With Quote
Old 2022-09-22, 17:07   #18
axn
 
axn's Avatar
 
Jun 2003

153316 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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?
axn is offline   Reply With Quote
Old 2022-09-22, 17:41   #19
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

808410 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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 View Post
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.
Prime95 is offline   Reply With Quote
Old 2022-09-22, 18:13   #20
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,413 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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?
ATH is online now   Reply With Quote
Old 2022-09-22, 19:53   #21
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22·43·47 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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 is offline   Reply With Quote
Old 2022-09-22, 20:33   #22
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22×43×47 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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
Prime95 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Group order not accepted for some GMP-ECM factors? rwwh FactorDB 2 2015-06-19 06:26
ECM curve group order Brain Miscellaneous Math 1 2010-12-08 01:00
What is this group? wpolly Math 1 2008-06-09 12:14
how to join a group gian92 Software 0 2008-02-22 21:08
Lie group E8 mapped ixfd64 Lounge 13 2007-03-23 15:06

All times are UTC. The time now is 20:28.


Tue Nov 29 20:28:07 UTC 2022 up 103 days, 17:56, 0 users, load averages: 0.71, 0.97, 0.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔