GMP-ECM vs mprime for F12?

[mathwiz]

I've been playing a bit with GMP-ECM vs. mprime for the remaining C1133 of F12.

It seems mprime's ECM mode is way faster (3 hours vs. 6+) on my Xeon. Why is this? Does it have some particular optimizations for Fermat numbers, the use of gwnum, something else?

[Prime95]

Yes, mprime uses the faster gwnum library vs. GMP for GMP-ECM.

However, GMP-ECM uses a superior algorithm for stage 2.

So, the optimal solution is to use mprime for stage 1 and GMP-ECM for stage 2. Dig around in the forums for instructions on how to do this.

Good luck in your search

[mathwiz]

It seems like compiling GMP-ECM with the --with-gwnum configuration option seems to (roughly) do the trick?

[Prime95]

Originally Posted by mathwiz

It seems like compiling GMP-ECM with the --with-gwnum configuration option seems to (roughly) do the trick?

Yes, but it may not work. As far as I know, no one has tried that for years.

[mathwiz]

Originally Posted by Prime95

Yes, but it may not work. As far as I know, no one has tried that for years.

Seems fine to me? Everything builds fine with the latest source...

GMP-ECM 7.0.4 [configured with GMP 6.1.2, GWNUM 29.4, --enable-asm-redc] [ECM]
Tuned for x86_64/k8/params.h
Due to incompatible licenses, this binary file must not be distributed.
Input number is (2^4096+1)/25860116183332395113497853167940236083358054650286886725246241569916604094012679963198712829716480001 (1133 digits)
Found number: 1*2^4096 + 1
Using special division for factor of 2^4096+1
Using B1=850000000, B2=15892628251516, polynomial x^1, sigma=0:17241075805006320821
dF=524288, k=5, d=5705700, d2=17, i0=132
Expected number of curves to find a factor of n digits:
35	40	45	50	55	60	65	70	75	80
16	51	183	729	3188	15164	77841	427872	2503667	1.6e+07
Using gwnum_ecmStage1(1, 2, 4096, 1, 850000000, 1)
Step 1 took 7762359ms
Estimated memory usage: 13.58GB
Initializing tables of differences for F took 3ms
Computing roots of F took 11918ms
Building F from its roots took 96743ms
Computing 1/F took 80569ms
Initializing table of differences for G took 140ms
Computing roots of G took 8681ms
Building G from its roots took 96779ms
Computing roots of G took 8755ms
Building G from its roots took 97078ms
Computing G * H took 50789ms
Reducing  G * H mod F took 96635ms
Computing roots of G took 9421ms
Building G from its roots took 114522ms
Computing G * H took 54272ms
Reducing  G * H mod F took 98293ms
Computing roots of G took 8740ms
Building G from its roots took 94358ms
Computing G * H took 49260ms
Reducing  G * H mod F took 98047ms
Computing roots of G took 8667ms
Building G from its roots took 93193ms
Computing G * H took 48465ms
Reducing  G * H mod F took 96023ms
Computing polyeval(F,G) took 283192ms
Computing product of all F(g_i) took 2667ms
Step 2 took 1609858ms
Expected time to find a factor of n digits:
35	40	45	50	55	60	65	70	75	80
1.78d	5.59d	19.89d	79.11d	345.78d	4.51y	23.13y	127.16y	744.07y	4613y

[Prime95]

Cool.

Can you test it to find known factors of F12? Maybe Xyzzy can dig up the sigma and bounds for his discovered factor.

[VBCurtis]

If this build finds known factors, I'm going to be finding some mersenne factors with it!
I wish you success, mathwiz.

[ATH]

Here is the sigma from the F14 factor:
https://mersenneforum.org/showpost.p...9&postcount=18

So you can test with:
ecm.exe -sigma 8585974330888598 110e6 110e8 < f14.txt

where f14.txt is just "2^16384+1"

[Prime95]

After you've completed a QA run, be aware that stage 1 (I can't comment on stage 2) is not multi-threaded. On a multi-core machine you'll want to be running several instances during stage 1.

Stage 2 where access to memory is critical you'll probably only want one instance running -- check with GMP-ECMers to see if this advice is accurate.

[mathwiz]

Originally Posted by ATH

Here is the sigma from the F14 factor:
https://mersenneforum.org/showpost.p...9&postcount=18

So you can test with:
ecm.exe -sigma 8585974330888598 110e6 110e8 < f14.txt

where f14.txt is just "2^16384+1"

Yup.

Input number is 2^16384+1 (4933 digits)
Found number: 1*2^16384 + 1
Using special division for factor of 2^16384+1
Using B1=110000000, B2=11000000000, polynomial x^1, sigma=0:8585974330888598
dF=16384, k=4, d=158340, d2=11, i0=684
Expected number of curves to find a factor of n digits:
35	40	45	50	55	60	65	70	75	80
73	308	1481	7942	46946	302925	2115419	1.6e+07	1.3e+08	1.1e+09
Using gwnum_ecmStage1(1, 2, 16384, 1, 110000000, 1)
Step 1 took 3102146ms
Estimated memory usage: 1.64GB
Initializing tables of differences for F took 13ms
Computing roots of F took 1634ms
Building F from its roots took 3879ms
Computing 1/F took 1515ms
Initializing table of differences for G took 139ms
Computing roots of G took 1282ms
Building G from its roots took 3860ms
Computing roots of G took 1282ms
Building G from its roots took 3860ms
Computing G * H took 844ms
Reducing  G * H mod F took 1269ms
Computing roots of G took 1283ms
Building G from its roots took 3853ms
Computing G * H took 843ms
Reducing  G * H mod F took 1268ms
Computing roots of G took 1282ms
Building G from its roots took 3879ms
Computing G * H took 846ms
Reducing  G * H mod F took 1270ms
Computing polyeval(F,G) took 8930ms
Computing product of all F(g_i) took 622ms
Step 2 took 43778ms
********** Factor found in step 2: 116928085873074369829035993834596371340386703423373313
Found prime factor of 54 digits: 116928085873074369829035993834596371340386703423373313
Composite cofactor (2^16384+1)/116928085873074369829035993834596371340386703423373313 has 4880 digits
Peak memory usage: 994MB

[mathwiz]

Interestingly, GMP-ECM only seems to use gwnum_ecmStage1() if the input is written out explicitly in (2^n +/- 1)/d form, as opposed to a full decimal. E.g.:

Input number is 7124875134919416452774071346240764917465050401053729788475829418006792633070197260773480462000925038600888030166963314178711084227927169505054967049906157236644045588489318562381444403587801123276191390920852492526599174604254696368010876509960456095578194840205874002033519141134093531142804832239163228700607998501023572045880402900991 (337 digits)
Did not find a gwnum poly for the input number.
Using special division for factor of 2^1243-1

but

Input number is (2^1243-1)/(2^113-1)/2047 (337 digits)
Found number: 1*2^1243 + -1
Using special division for factor of 2^1243-1
Using B1=850000000, B2=15892628251516, polynomial Dickson(30), sigma=0:10702604903946832294
dF=524288, k=5, d=5705700, d2=17, i0=132
Expected number of curves to find a factor of n digits:
35	40	45	50	55	60	65	70	75	80
15	47	168	661	2867	13623	69471	381778	2221086	1.4e+07
Using gwnum_ecmStage1(1, 2, 1243, -1, 850000000, 1)