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

 2022-09-18, 01:54 #1 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 23×1,021 Posts ECM group order mystery 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>
2022-09-18, 06:07   #2
axn

Jun 2003

543810 Posts

Quote:
 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
Code:
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]

 2022-09-18, 18:13 #3 frmky     Jul 2003 So Cal 50548 Posts 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.
2022-09-18, 18:23   #4
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

23×1,021 Posts

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

2022-09-18, 18:51   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3·3,889 Posts

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

2022-09-19, 00:01   #6
bbb120

"特朗普trump"
Feb 2019

2048 Posts

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

Last fiddled with by bbb120 on 2022-09-19 at 00:02

 2022-09-19, 00:11 #7 VBCurtis     "Curtis" Feb 2005 Riverside, CA 33·11·19 Posts If we knew why, we wouldn't have a mystery now, would we?
 2022-09-19, 10:06 #8 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 17·79 Posts 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.
 2022-09-19, 12:22 #9 Neptune     "Martin Hopf" Jul 2022 Germany 2·3·7 Posts Looking at the parameterization of the curve between line 3232 and 3305 in ecm.cpp (version 30.8b15): u = sig2 - 5 v = 4sig; x = u3 z = v3 An = (v - u)3 (3u + v) Ad4 = 4u3 v seems all OK to me up to here, but for: /* Normalize so that An is one */ 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 = sig2 - 5 v = 4sig; x = u3 z = v3 An = (v - u)3 (3u + v) all as above but now: Ad4 = 16u3 v and /* Normalize so that Ad4 is one */ Ad4 = An ( (1 / Ad4) % n) That's all nothing more needs to be changed. Last fiddled with by Neptune on 2022-09-19 at 12:25 Reason: clarification. Btw how much time do i have for editing ? Need endless :)
2022-09-19, 13:33   #10
axn

Jun 2003

153E16 Posts

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

 2022-09-19, 22:11 #11 ATH Einyen     Dec 2003 Denmark 19·181 Posts GMP-ECM does not find it with that sigma: Code: 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

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

Wed Feb 8 18:18:51 UTC 2023 up 174 days, 15:47, 1 user, load averages: 1.97, 1.30, 1.12