20201123, 08:29  #1 
Oct 2007
Manchester, UK
1343_{10} Posts 
Expected behaviour or bug? Higher B2 = missed factor
I've been doing some testing & tweaking with ECM settings for some numbers I'm crunching lately and have encountered this confusing behaviour. My understanding of ECM is fairly naive, essentially "moar B2 = moar factors*" (*with diminishing returns, extra run time, memory, etc etc).
However I have found a factor with a certain B2, which then is NOT found with a higher B2. If it's relevent, I'm using ECM 7.0.5dev compiled with this script provided by ATH. If anyone wants to try it, this is the number: Code:
1742286317399290628231773504346807706377474566602136857214187842480908604771754085247050453433233497474002335637056340765565286971906100271 Code:
ecm v sigma 3:479786000 k 2 1e6 1e9 < in_test.txt >> out_test.txt ecm v sigma 3:479786000 k 2 1e6 5e9 < in_test.txt >> out_test.txt Code:
GMPECM 7.0.5dev [configured with GMP 6.1.2, enableasmredc] [ECM] Input number is 1742286317399290628231773504346807706377474566602136857214187842480908604771754085247050453433233497474002335637056340765565286971906100271 (139 digits) Using MODMULN [mulredc:0, sqrredc:1] Computing batch product (of 1442099 bits) of primes up to B1=1000000 took 16ms Using B1=1000000, B2=1000000000, polynomial Dickson(6), sigma=3:479786000 dF=8192, k=2, d=79170, d2=11, 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 1099 10576 121716 1614533 2.4e+07 4e+008 8e+009 3.2e+11 5.3e+16 7.2e+21 Step 1 took 1578ms Using 18 small primes for NTT Estimated memory usage: 31.94MB Step 2 took 1250ms ********** Factor found in step 2: 3066550416835308999556846085835246061 Found prime factor of 37 digits: 3066550416835308999556846085835246061 Prime cofactor 568158380124510178651545326996915368807245497112562111204520271418133764969686490599793112450876537611 has 102 digits Peak memory usage: 37MB Code:
GMPECM 7.0.5dev [configured with GMP 6.1.2, enableasmredc] [ECM] Input number is 1742286317399290628231773504346807706377474566602136857214187842480908604771754085247050453433233497474002335637056340765565286971906100271 (139 digits) Using MODMULN [mulredc:0, sqrredc:1] Computing batch product (of 1442099 bits) of primes up to B1=1000000 took 15ms Using B1=1000000, B2=5000000000, polynomial Dickson(6), sigma=3:479786000 dF=16384, k=2, d=158340, d2=11, i0=4 Expected number of curves to find a factor of n digits (assuming one exists): 35 40 45 50 55 60 65 70 75 80 822 7745 87603 1144424 1.7e+07 2.8e+08 5.4e+09 1.4e+11 1.3e+16 1.8e+21 Step 1 took 1610ms Using 18 small primes for NTT Estimated memory usage: 57.31MB Step 2 took 2765ms Expected time to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 59.91m 9.41h 4.44d 57.95d 2.37y 38.86y 752.64y 19712y 2e+009y 2e+014y Peak memory usage: 73MB Separate rant now, the output used to show you what the REAL calculated B2 value used was, it'd be nice to get that back. Additionally the "Expected number of curves" is calculated based on the nice rounded bounds specified in the command line, not the real bounds used which seems wrong. In the second case I could say B2 is anywhere from 2 billion to 5.7 billion and it will do the exact same work, but it'll say I need a lot more curves to find factors with 2e9, which isn't actually true. 
20201123, 09:19  #2 
Jul 2003
So Cal
2,083 Posts 
The group order factors as 2^6 * 5 * 7 * 1483 * 1783 * 1913 * 1973 * 88339 * 196379 * 7907150747 so it should always be found with B1=2e5, B2=8e9. Not sure why B2=1e9 works, though.

20201123, 09:29  #3 
Jun 2003
1001100110101_{2} Posts 

20201123, 13:12  #4  
Oct 2007
Manchester, UK
17·79 Posts 
Quote:
Using the code provided here or using FactorDB to calculate it, I get this group order: Code:
2^2 * 3^2 * 7^2 * 11^3 * 97 * 191 * 151817 * 407691919 * 1138979383393 Code:
Err: Calculated grouporder 3066550416835308997986903239781335052<37> is not within B1/B2 bounds (B1=1000000, B2=1400000000). Please check your result! 

20201123, 20:33  #5 
Jul 2003
So Cal
2,083 Posts 
Using Tom's code modified for a param 3 sigma.
Code:
FindGroupOrder2 := function (p, s) K := GF(p); x := K ! 2; b := K ! 2^32; a := K ! 4*s; A := a/b2; b := x^3 + A*x^2 + x; E := EllipticCurve([0,b*A,0,b^2,0]); return FactoredOrder(E); end function; p := 3066550416835308999556846085835246061; s := 479786000; FindGroupOrder2(p, s); 
20201124, 03:35  #6 
Oct 2007
Manchester, UK
17·79 Posts 
Ah, thankyou for the alternate parameterization code.
While I don't fully understand the code, I believe I've managed to translate it into pari/gp. In particular, nowhere seems to clarify exactly what the exclamation mark operator does in Magma, but I gather it's something along the lines of "put this in the field" ala modular arithmetic. I'll post my code here in case anyone is interested, but this is also for myself when I search back through the forum to find it. If I've made any mistakes or if it could be calculated in a faster/more optimal way with pari I'd appreciate any improvements anyone might care to suggest. The nice thing about a pari script is that I can call it from the command line or from a batch file and autogenerate some stats about found factors. Code:
FindGroupOrder2(p, s) = { v = Mod(4*s, p); u = Mod(s*s5, p); x = u^3; A = (3*u+v)*(vu)^3 / (4*x*v)  2; x = x/v^3; b = x*(x*(x + A) + 1); E = ellinit([0,b*A,0,b^2,0]); ellcard(E); } FindGroupOrder3(p, s) = { A = Mod(4*s, p)/2^32  2; b = 4*A + 10; E = ellinit([0,b*A,0,b^2,0]); ellcard(E); } p = 26757495525262452858412972724728927157469061956724253045372193707; s = 3963355728406564; order = FindGroupOrder2(p, s); print(order); print(factor(order)); p = 3066550416835308999556846085835246061; s = 479786000; order = FindGroupOrder3(p, s); print(order); print(factor(order)); 
20201204, 00:20  #7  
Nov 2020
1 Posts 
Quote:
do I need some library to implement it or the problem lies in my PC? 

20201204, 02:22  #8 
Oct 2007
Manchester, UK
17·79 Posts 
I've tried it on a couple of PCs now with just the default installation of pari/gp and they both ran it fine. One running Windows 7 and pari 2.9.4, the other Windows 10 and pari 2.13.0. It's possible you may need to update but without seeing the error I wouldn't know.
Edit: I have also repackaged the code a little neater so that group order may be calculated with either parameterisation from the same function: Code:
FindGroupOrder(p, s, param=1) = { A = Mod(0, 3); b = Mod(1, 3); if(param==1, v = Mod(4*s, p); u = Mod(s^25, p); x = u^3; A = (3*u+v)*(vu)^3 / (4*x*v)  2; x = x/v^3; b = x*(x*(x + A) + 1), param==3, A = Mod(4*s, p)/2^32  2; b = 4*A + 10; ); E = ellinit([0,b*A,0,b^2,0]); ellcard(E) } Last fiddled with by lavalamp on 20201204 at 02:31 
20201204, 06:01  #9 
Aug 2006
3^{2}×5×7×19 Posts 

20201204, 07:49  #10 
Oct 2007
Manchester, UK
17×79 Posts 
I decided to dig in to the ECM code and look for the various parameterisations. It appears that what my previous code referred to as parameter 1, should have been parameter 0.
These are the parameterisations used by ECM as defined in ecm.h: Code:
#define ECM_PARAM_SUYAMA 0 #define ECM_PARAM_BATCH_SQUARE 1 #define ECM_PARAM_BATCH_2 2 #define ECM_PARAM_BATCH_32BITS_D 3 /* we keep 4 as spare */ #define ECM_PARAM_WEIERSTRASS 5 #define ECM_PARAM_HESSIAN 6 #define ECM_PARAM_TORSION 7 I suppose this should be considered version 0.3 now. Code:
FindGroupOrder(p, s, param=0) = { A = 0; b = 0; if(param==0, v = Mod(4 * s, p); u = Mod(s^2  5, p); x = u^3; A = (3 * u + v) * (v  u)^3 / (4 * x * v)  2; x = x / v^3; b = x * (x * (x + A) + 1), param==1, A = Mod(4 * s^2, p) / 2^64  2; b = 4 * A + 10, param==2, E = ellinit([0, Mod(36, p)]); [x, y] = ellmul(E, [3, 3], s); x3 = (3 * x + y + 6) / (2 * (y  3)); A = (3 * x3^4 + 6 * x3^2  1) / (4 * x3^3); b = 1 / (4 * A + 10), param==3, A = Mod(4 * s, p) / 2^32  2; b = 4 * A + 10; ); if(param>=0 && param<=3, E = ellinit([0, b * A, 0, b^2, 0]); ellcard(E), 0 ) } 
20201208, 10:43  #11 
"Oliver"
Sep 2017
Porta Westfalica, DE
2^{2}×3^{2}×13 Posts 
Thanks for the script! To get it working, I had to replace all tabs with spaces.
Code:
FindGroupOrder(p, s, param=0) = { A = 0; b = 0; if (param==0, v = Mod(4 * s, p); u = Mod(s^2  5, p); x = u^3; A = (3 * u + v) * (v  u)^3 / (4 * x * v)  2; x = x / v^3; b = x * (x * (x + A) + 1), param==1, A = Mod(4 * s^2, p) / 2^64  2; b = 4 * A + 10, param==2, E = ellinit([0, Mod(36, p)]); [x, y] = ellmul(E, [3, 3], s); x3 = (3 * x + y + 6) / (2 * (y  3)); A = (3 * x3^4 + 6 * x3^2  1) / (4 * x3^3); b = 1 / (4 * A + 10), param==3, A = Mod(4 * s, p) / 2^32  2; b = 4 * A + 10; ); if (param>=0 && param<=3, E = ellinit([0, b * A, 0, b^2, 0]); ellcard(E), 0 ) } 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
If you were expected to work, but not expected to get a job or pay, what would be good things to do?  jasong  Lounge  10  20180604 16:39 
Factor missed by TF  bcp19  PrimeNet  15  20150810 11:57 
P1 Missed factor  tha  Data  7  20140430 20:54 
missed factor?  tha  Data  76  20140317 17:42 
mfaktc TF credit 2x higher if factor found?  S34960zz  PrimeNet  10  20111013 07:00 