mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2020-11-23, 08:29   #1
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2·3·223 Posts
Question 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.
lavalamp is offline   Reply With Quote
Old 2020-11-23, 09:19   #2
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

1000000001102 Posts
Default

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.
frmky is offline   Reply With Quote
Old 2020-11-23, 09:29   #3
axn
 
axn's Avatar
 
Jun 2003

113528 Posts
Default

Quote:
Originally Posted by frmky View Post
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.
axn is offline   Reply With Quote
Old 2020-11-23, 13:12   #4
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2×3×223 Posts
Default

Quote:
Originally Posted by frmky View Post
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!
lavalamp is offline   Reply With Quote
Old 2020-11-23, 20:33   #5
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2·13·79 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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/.
frmky is offline   Reply With Quote
Old 2020-11-24, 03:35   #6
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

53A16 Posts
Default

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));
lavalamp is offline   Reply With Quote
Old 2020-12-04, 00:20   #7
simonss22
 
Nov 2020

110 Posts
Default

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?
simonss22 is offline   Reply With Quote
Old 2020-12-04, 02:22   #8
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

2×3×223 Posts
Default

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
lavalamp is offline   Reply With Quote
Old 2020-12-04, 06:01   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,987 Posts
Default

CRGreathouse is offline   Reply With Quote
Old 2020-12-04, 07:49   #10
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

53A16 Posts
Default

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.
lavalamp is offline   Reply With Quote
Old 2020-12-08, 10:43   #11
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

2·7·29 Posts
Default

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.
kruoli is offline   Reply With Quote
Reply

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 2018-06-04 16:39
Factor missed by TF bcp19 PrimeNet 15 2015-08-10 11:57
P-1 Missed factor tha Data 7 2014-04-30 20:54
missed factor? tha Data 76 2014-03-17 17:42
mfaktc TF credit 2x higher if factor found? S34960zz PrimeNet 10 2011-10-13 07:00

All times are UTC. The time now is 11:55.

Mon Jan 18 11:55:43 UTC 2021 up 46 days, 8:07, 0 users, load averages: 2.54, 2.66, 2.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.