mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   FermatSearch (https://www.mersenneforum.org/forumdisplay.php?f=133)
-   -   GMP-ECM vs mprime for F12? (https://www.mersenneforum.org/showthread.php?t=24160)

mathwiz 2019-03-09 23:44

GMP-ECM vs mprime for F12?
 
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 2019-03-10 03:28

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 2019-03-11 15:46

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

Prime95 2019-03-11 19:05

[QUOTE=mathwiz;510598]It seems like compiling GMP-ECM with the --with-gwnum configuration option seems to (roughly) do the trick?[/QUOTE]

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

mathwiz 2019-03-12 00:40

[QUOTE=Prime95;510609]Yes, but it may not work. As far as I know, no one has tried that for years.[/QUOTE]

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

[code]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[/code]

Prime95 2019-03-12 03:14

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 2019-03-12 04:29

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

ATH 2019-03-12 06:34

Here is the sigma from the F14 factor:
[url]https://mersenneforum.org/showpost.php?p=204429&postcount=18[/url]

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

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

Prime95 2019-03-12 14:00

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 2019-03-12 19:57

[QUOTE=ATH;510639]Here is the sigma from the F14 factor:
[url]https://mersenneforum.org/showpost.php?p=204429&postcount=18[/url]

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

where f14.txt is just "2^16384+1"[/QUOTE]

Yup.

[code]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[/code]

mathwiz 2019-03-13 04:49

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

[code]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[/code]

but

[code]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)[/code]


All times are UTC. The time now is 07:21.

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