mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2019-03-09, 23:44   #1
mathwiz
 
Mar 2019

127 Posts
Default 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?
mathwiz is offline   Reply With Quote
Old 2019-03-10, 03:28   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23·3·7·43 Posts
Default

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
Prime95 is offline   Reply With Quote
Old 2019-03-11, 15:46   #3
mathwiz
 
Mar 2019

1778 Posts
Default

It seems like compiling GMP-ECM with the --with-gwnum configuration option seems to (roughly) do the trick?
mathwiz is offline   Reply With Quote
Old 2019-03-11, 19:05   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

722410 Posts
Default

Quote:
Originally Posted by mathwiz View Post
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.
Prime95 is offline   Reply With Quote
Old 2019-03-12, 00:40   #5
mathwiz
 
Mar 2019

127 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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...

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
mathwiz is offline   Reply With Quote
Old 2019-03-12, 03:14   #6
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1C3816 Posts
Default

Cool.

Can you test it to find known factors of F12? Maybe Xyzzy can dig up the sigma and bounds for his discovered factor.
Prime95 is offline   Reply With Quote
Old 2019-03-12, 04:29   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

11×409 Posts
Default

If this build finds known factors, I'm going to be finding some mersenne factors with it!
I wish you success, mathwiz.
VBCurtis is online now   Reply With Quote
Old 2019-03-12, 06:34   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·3·7·71 Posts
Default

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"
ATH is offline   Reply With Quote
Old 2019-03-12, 14:00   #9
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23·3·7·43 Posts
Default

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.
Prime95 is offline   Reply With Quote
Old 2019-03-12, 19:57   #10
mathwiz
 
Mar 2019

127 Posts
Default

Quote:
Originally Posted by ATH View Post
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.

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
mathwiz is offline   Reply With Quote
Old 2019-03-13, 04:49   #11
mathwiz
 
Mar 2019

7F16 Posts
Default

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
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)
mathwiz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
mprime Unregistered Information & Answers 3 2011-08-05 09:17
mPrime over SSH Vincanis Information & Answers 4 2011-06-30 13:36
ECM using gmp-ecm and mprime on a P4 geoff Factoring 60 2004-12-02 07:16
mprime talcum Software 6 2004-08-04 18:25
Problem with mprime (Fixed with mprime -d) antiroach Software 2 2004-07-19 04:07

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

Wed Dec 2 07:25:57 UTC 2020 up 83 days, 4:36, 1 user, load averages: 1.57, 1.34, 1.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.