Expected behaviour or bug? Higher B2 = missed factor

[lavalamp]

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:

1742286317399290628231773504346807706377474566602136857214187842480908604771754085247050453433233497474002335637056340765565286971906100271

And these are the commands I ran:

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:

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:

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.

[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.

[axn]

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.

[lavalamp]

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:

2^2 * 3^2 * 7^2 * 11^3 * 97 * 191 * 151817 * 407691919 * 1138979383393

FactorDB also helpfully tells me that:

Err: Calculated grouporder 3066550416835308997986903239781335052<37> is not within B1/B2 bounds (B1=1000000, B2=1400000000). Please check your result!

[frmky]

Originally Posted by lavalamp

How did you calculate this?

Using Tom's code modified for a param 3 sigma.

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/.

[lavalamp]

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.

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));

[simonss22]

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?

[lavalamp]

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:

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)?

[CRGreathouse]

[lavalamp]

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:

#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.

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.

[kruoli]

Thanks for the script! To get it working, I had to replace all tabs with spaces.

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.