mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-11-05, 20:26   #23
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×3×1,699 Posts
Default

Quote:
Originally Posted by ryanp View Post
This thread is.. strange.
xilman is online now   Reply With Quote
Old 2020-11-05, 20:41   #24
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

9A916 Posts
Default

*Acoustic guitar mode on*

Last fiddled with by firejuggler on 2020-11-05 at 20:44
firejuggler is online now   Reply With Quote
Old 2020-11-05, 20:55   #25
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

22·53 Posts
Default

Quote:
Originally Posted by bsquared View Post
Sparing me the build process to figure it out for myself, does GWNUM provide a speedup even for "small" inputs like 2^1277-1? How about 2^941-1? Wondering where the cutoff is to normal mulmod methods.

(Small, of course, relative to where prime95 usually operates.)
Attempting to get something useful out of this thread, here are some timings on a 2Ghz Skylake VM. Without GWNUM:

Code:
$ echo "2^1277-1" | ./ecm -c 5 11e6
GMP-ECM 7.0.4 [configured with GMP 6.2.0, --enable-asm-redc] [ECM]
Input number is 2^1277-1 (385 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:15382913345576557885
Step 1 took 63126ms
Step 2 took 28310ms
Run 2 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:2472923556820086104
Step 1 took 63697ms
Step 2 took 28330ms
Run 3 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:13772778279637613489
Step 1 took 63532ms
Step 2 took 28339ms
Run 4 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:4149983287909296098
Step 1 took 65040ms
Step 2 took 28394ms
Run 5 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:3089621796835281869
Step 1 took 65407ms
Step 2 took 28430ms
With GWNUM linked:

Code:
$ echo "2^1277-1" | ./ecm -c 5 11e6
GMP-ECM 7.0.4 [configured with GMP 6.2.0, GWNUM 29.8, --enable-asm-redc] [ECM]
Due to incompatible licenses, this binary file must not be distributed.
Input number is 2^1277-1 (385 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:1133017334638497343
Step 1 took 52939ms
Step 2 took 28574ms
Run 2 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:16936162798099609109
Step 1 took 52935ms
Step 2 took 28488ms
Run 3 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:4745769159583183902
Step 1 took 52719ms
Step 2 took 28706ms
Run 4 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:14575819613407288447
Step 1 took 52688ms
Step 2 took 28512ms
Run 5 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=0:7117923393329265041
Step 1 took 52795ms
Step 2 took 28585ms
So, a decent speedup in stage 1.
ryanp is offline   Reply With Quote
Old 2020-11-05, 21:06   #26
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Thanks, that's unexpected but neat. Wonder where the crossover is...
bsquared is offline   Reply With Quote
Old 2020-11-05, 23:01   #27
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

22·53 Posts
Default

Quote:
Originally Posted by bsquared View Post
Thanks, that's unexpected but neat. Wonder where the crossover is...
With larger inputs and B1's, the speedup is even more dramatic:

Code:
$ echo "2^2267-1" | ./ecm -c 5 43e6
GMP-ECM 7.0.4 [configured with GMP 6.2.0, --enable-asm-redc] [ECM]
Input number is 2^2267-1 (683 digits)
Using B1=43000000, B2=198654756318, polynomial Dickson(12), sigma=0:12068850290356100037
Step 1 took 546568ms
Step 2 took 163563ms
vs.

Code:
$ echo "2^2267-1" | ./ecm -c 5 43e6
GMP-ECM 7.0.4 [configured with GMP 6.2.0, GWNUM 29.8, --enable-asm-redc] [ECM]
Due to incompatible licenses, this binary file must not be distributed.
Input number is 2^2267-1 (683 digits)
Using B1=43000000, B2=198654756318, polynomial Dickson(12), sigma=0:16623107045151173302
Step 1 took 250555ms
Step 2 took 163852ms
Over twice as fast in B1!
ryanp is offline   Reply With Quote
Old 2020-11-06, 00:10   #28
bbb120
 
bbb120's Avatar
 
Feb 2019
China

728 Posts
Default

Quote:
Originally Posted by ryanp View Post
This thread is.. strange.
not strange,
I take Great curiosity on primality and integer factorization.
bbb120 is offline   Reply With Quote
Old 2020-11-06, 01:49   #29
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

22×53 Posts
Default

Quote:
Originally Posted by bbb120 View Post
not strange,
I take Great curiosity on primality and integer factorization.
Me, too!
ryanp is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 18:58.

Thu Nov 26 18:58:02 UTC 2020 up 77 days, 16:09, 3 users, load averages: 1.25, 1.43, 1.52

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.