20220918, 01:54  #1 
P90 years forever!
Aug 2002
Yeehaw, FL
17744_{8} 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> 
20220918, 06:07  #2 
Jun 2003
2×2,719 Posts 
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^25; x=u^3; b=4*x*v; a=(vu)^3*(3*u+v); A=a/b2; 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] 
20220918, 18:13  #3 
Jul 2003
So Cal
2×1,301 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. 
20220918, 18:23  #4 
P90 years forever!
Aug 2002
Yeehaw, FL
2^{2}×13×157 Posts 
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. 
20220918, 18:51  #5  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
11662_{10} Posts 
Quote:


20220919, 00:01  #6  
"特朗普trump"
Feb 2019
朱晓丹没人草
84_{16} Posts 
Quote:
and it is really very interesting (B2<<100350976151081387<18>) Last fiddled with by bbb120 on 20220919 at 00:02 

20220919, 00:11  #7 
"Curtis"
Feb 2005
Riverside, CA
5,639 Posts 
If we knew why, we wouldn't have a mystery now, would we?

20220919, 10:06  #8 
"Oliver"
Sep 2017
Porta Westfalica, DE
2^{2}·3^{2}·37 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 oneoff.

20220919, 12:22  #9 
"Martin Hopf"
Jul 2022
Germany
2A_{16} Posts 
Looking at the parameterization of the curve between line 3232 and 3305 in ecm.cpp (version 30.8b15):
u = sig^{2}  5 v = 4sig; x = u^{3} z = v^{3} An = (v  u)^{3 }(3u + v) Ad4 = 4u^{3 }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 = A2 in the last step we can ommit A2 / A+2 and multiply the denomintaor Ad4 with four. Then one normalization in the last step to get the right parameterization: u = sig^{2}  5 v = 4sig; x = u^{3} z = v^{3} An = (v  u)^{3 }(3u + v) all as above but now: Ad4 = 16u^{3 }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 20220919 at 12:25 Reason: clarification. Btw how much time do i have for editing ? Need endless :) 
20220919, 13:33  #10  
Jun 2003
12476_{8} Posts 
Quote:
I just searched nearby values for sigmas that work. s+18 and s+2^168 (1bit hamming distance) work. Of course it proves nothing. If we search enough sigmas, we'll get some that work. 

20220919, 22:11  #11 
Einyen
Dec 2003
Denmark
19×181 Posts 
GMPECM does not find it with that sigma:
Code:
ecm.exe c 1 v savea M257189out.txt maxmem 12000 sigma 8055078829352661 1e6 2842011315 < M257189.txt GMPECM 7.0.5dev [configured with GMP 6.2.1, enableasmredc] [ECM] Input number is 2^2571891 (77422 digits) Using special division for factor of 2^2571891 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Group order not accepted for some GMPECM factors?  rwwh  FactorDB  2  20150619 06:26 
ECM curve group order  Brain  Miscellaneous Math  1  20101208 01:00 
What is this group?  wpolly  Math  1  20080609 12:14 
how to join a group  gian92  Software  0  20080222 21:08 
Lie group E8 mapped  ixfd64  Lounge  13  20070323 15:06 