mersenneforum.org Expected behaviour or bug? Higher B2 = missed factor
 Register FAQ Search Today's Posts Mark Forums Read

 2020-11-23, 08:29 #1 lavalamp     Oct 2007 Manchester, UK 2·3·223 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.5-dev compiled with this script provided by ATH. If anyone wants to try it, this is the number: Code: 1742286317399290628231773504346807706377474566602136857214187842480908604771754085247050453433233497474002335637056340765565286971906100271 And these are the commands I ran: 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 This is the slightly trimmed output of each, first a success with the smaller B2: Code: GMP-ECM 7.0.5-dev [configured with GMP 6.1.2, --enable-asm-redc] [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 And the miss with a higher B2: Code: GMP-ECM 7.0.5-dev [configured with GMP 6.1.2, --enable-asm-redc] [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.
 2020-11-23, 09:19 #2 frmky     Jul 2003 So Cal 3×5×137 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.
2020-11-23, 09:29   #3
axn

Jun 2003

3×5×17×19 Posts

Quote:
 Originally Posted by frmky 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.
Brent-Suyama. Very much a lottery.

2020-11-23, 13:12   #4
lavalamp

Oct 2007
Manchester, UK

2×3×223 Posts

Quote:
 Originally Posted by frmky 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.
How did you calculate this?

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
FactorDB also helpfully tells me that:
Code:
Err: Calculated grouporder 3066550416835308997986903239781335052<37> is not within B1/B2 bounds (B1=1000000, B2=1400000000). Please check your result!

2020-11-23, 20:33   #5
frmky

Jul 2003
So Cal

3×5×137 Posts

Quote:
 Originally Posted by lavalamp How did you calculate this?
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/b-2;
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);
Run it at http://magma.maths.usyd.edu.au/calc/.

 2020-11-24, 03:35 #6 lavalamp     Oct 2007 Manchester, UK 24728 Posts Ah, thank-you 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 auto-generate some stats about found factors. Code: FindGroupOrder2(p, s) = { v = Mod(4*s, p); u = Mod(s*s-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); 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));
2020-12-04, 00:20   #7
simonss22

Nov 2020

1 Posts

Quote:
 Ah, thank-you for the alternate parameterization code. While I don't fully understand the code, I believe I've managed to translate it into pari/gp. ...
somehow while trying to use your code I received and unknown error
do I need some library to implement it or the problem lies in my PC?

 2020-12-04, 02:22 #8 lavalamp     Oct 2007 Manchester, UK 101001110102 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^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==3, A = Mod(4*s, p)/2^32 - 2; b = 4*A + 10; ); E = ellinit([0,b*A,0,b^2,0]); ellcard(E) } Does anyone know the parameterisation for when param=2 (or for any other values if there are any)? Last fiddled with by lavalamp on 2020-12-04 at 02:31
 2020-12-04, 06:01 #9 CRGreathouse     Aug 2006 3×1,987 Posts
 2020-12-04, 07:49 #10 lavalamp     Oct 2007 Manchester, UK 2×3×223 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've fixed the mis-matched parameter, and implemented params 1 and 2. They seem to be correct but if a 3rd party could verify that I'd appreciate it! 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 ) } I may have a bash at implementing params 5-7 in future.
 2020-12-08, 10:43 #11 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 11×37 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 ) } So you don't have to do it yourself, but full credits to lavalamp.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 10 2018-06-04 16:39 bcp19 PrimeNet 15 2015-08-10 11:57 tha Data 7 2014-04-30 20:54 tha Data 76 2014-03-17 17:42 S34960zz PrimeNet 10 2011-10-13 07:00

All times are UTC. The time now is 19:31.

Fri Jan 22 19:31:30 UTC 2021 up 50 days, 15:42, 0 users, load averages: 1.56, 2.11, 2.15

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.