mersenneforum.org  

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

Reply
 
Thread Tools
Old 2010-07-26, 01:06   #1
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

14168 Posts
Default Best settings to factor Wagstaff p = (2^n +1) / 1

hi thanks for the previous reactions, it helped.

I'm looking now for the best manner to factor wagstaffs, starting with very small ones, as i want to benchmark against my upcoming own tries.

Already when i try a composite exponent of 151 i stumble upon problems.

What parameters are best to try you guess to factor a bunch of wagstaffs?

Of course i toy now in the 'hundreds of bits' ranges, intention is to produce something later on that works for the real wagstaffs (we are testing now far above 4M bits actually with Wagstaff) to be used after the trial factorisation.

See the problems i run into here:

C:\factor\ecm>echo {(2^^^^101 + 1) / 3} | ecm 1000000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^101+1)/3} (30 digits)
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=3143366420
Step 1 took 2449ms
Step 2 took 1872ms

C:\factor\ecm>echo {(2^^^^97 + 1) / 3} | ecm 1000000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^97+1)/3} (29 digits)
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=540631553
Step 1 took 2449ms
********** Factor found in step 1: 47978858771
Found composite factor of 11 digits: 47978858771
Probable prime cofactor ({(2^97+1)/3})/47978858771 has 19 digits

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 1000000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=3604336760
Step 1 took 2776ms
Step 2 took 2372ms

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 10000000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=10000000, B2=35132741290, polynomial Dickson(12), sigma=1589823146
Step 1 took 27753ms
Step 2 took 20389ms

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 100000000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=100000000, B2=776268975310, polynomial Dickson(30), sigma=3046160105

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 100000000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=100000000, B2=776268975310, polynomial Dickson(30), sigma=3046160105
Step 1 took 281582ms
********** Factor found in step 1: 18717738334417
Found probable prime factor of 14 digits: 18717738334417
Probable prime cofactor ({(2^151+1)/3})/18717738334417 has 32 digits

You know just for 14 digits it needs 281 seconds.

I wouldn't say that with this in Peoples Republic of China produced wooden abacus i can do it faster but...
Attached Thumbnails
Click image for larger version

Name:	telraam.jpg
Views:	233
Size:	132.8 KB
ID:	5511  

Last fiddled with by diep on 2010-07-26 at 01:06
diep is offline   Reply With Quote
Old 2010-07-26, 01:08   #2
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×5×293 Posts
Default

Try a smaller B1 like
Code:
echo {(2^^^^151 + 1) / 3} | ecm 100000
Even B1=10000 can do it!

Last fiddled with by kar_bon on 2010-07-26 at 01:09
kar_bon is offline   Reply With Quote
Old 2010-07-26, 01:14   #3
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

30E16 Posts
Default

Quote:
Originally Posted by kar_bon View Post
Try a smaller B1 like
Code:
echo {(2^^^^151 + 1) / 3} | ecm 100000
Even B1=10000 can do it!
You sure?

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 10000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=10000, B2=1873422, polynomial x^1, sigma=878803321
Step 1 took 31ms
Step 2 took 47ms

C:\fail\>
diep is offline   Reply With Quote
Old 2010-07-26, 01:18   #4
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×5×293 Posts
Default

Quote:
Originally Posted by diep View Post
You sure?

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 10000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=10000, B2=1873422, polynomial x^1, sigma=878803321
Step 1 took 31ms
Step 2 took 47ms

C:\fail\>
Yes!

Code:
E:\ecm>echo {(2^^^^151 + 1) / 3} | ecm 10000
GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=10000, B2=1873422, polynomial x^1, sigma=184170618
Step 1 took 47ms
Step 2 took 31ms
********** Factor found in step 2: 18717738334417
Found probable prime factor of 14 digits: 18717738334417
Probable prime cofactor ({(2^151+1)/3})/18717738334417 has 32 digits
Try it more then once!
Do you know something more about the ECM-algorithm? Read first more about it, like using the B1-param!

Last fiddled with by kar_bon on 2010-07-26 at 01:19
kar_bon is offline   Reply With Quote
Old 2010-07-26, 01:26   #5
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

11000011102 Posts
Smile

Quote:
Originally Posted by kar_bon View Post
Yes!

Code:
E:\ecm>echo {(2^^^^151 + 1) / 3} | ecm 10000
GMP-ECM 6.2.3 [powered by GMP 4.3.0] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=10000, B2=1873422, polynomial x^1, sigma=184170618
Step 1 took 47ms
Step 2 took 31ms
********** Factor found in step 2: 18717738334417
Found probable prime factor of 14 digits: 18717738334417
Probable prime cofactor ({(2^151+1)/3})/18717738334417 has 32 digits
Try it more then once!
Do you know something more about the ECM-algorithm? Read first more about it, like using the B1-param!
Ah i see, ECM has a high degree of "i feel so lucky" push-button technology inside... ...after a few tries :)

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 1000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=1000, B2=51606, polynomial x^1, sigma=42049832
Step 1 took 0ms
Step 2 took 0ms

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 1000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=1000, B2=51606, polynomial x^1, sigma=3032908584
Step 1 took 0ms
Step 2 took 0ms

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 1000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=1000, B2=51606, polynomial x^1, sigma=948727984
Step 1 took 0ms
Step 2 took 16ms

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 1000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=1000, B2=51606, polynomial x^1, sigma=3156401853
Step 1 took 0ms
Step 2 took 15ms

C:\factor\ecm>echo {(2^^^^151 + 1) / 3} | ecm 1000
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [ECM]
Input number is {(2^151+1)/3} (45 digits)
Using B1=1000, B2=51606, polynomial x^1, sigma=2553158111
Step 1 took 0ms
Step 2 took 16ms
********** Factor found in step 2: 18717738334417
Found probable prime factor of 14 digits: 18717738334417
Probable prime cofactor ({(2^151+1)/3})/18717738334417 has 32 digits

C:\factor\ecm>
diep is offline   Reply With Quote
Old 2010-07-26, 06:48   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Firstly, you used B1=1000 not 10000 for those last 5 runs.
Secondly, you can tell ECM to run more than one curve with the -c <number_of_curves> switch.

Last fiddled with by 10metreh on 2010-07-26 at 06:48
10metreh is offline   Reply With Quote
Old 2010-07-26, 13:47   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by kar_bon View Post
Do you know something more about the ECM-algorithm? Read first more about it, like using the B1-param!
I know from long experience that most people never bother to
read/understand the algorithms and code that they use.
R.D. Silverman is offline   Reply With Quote
Old 2010-07-26, 14:24   #8
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

1011011100102 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I know from long experience that most people never bother to read/understand the algorithms and code that they use.
I mean, before I use a program, I should know how to use it's parameters, read more about it from internet or this forum here, trying to learn about it, try others programs which do the same.

After this is all done, I would ask for help.
Sure, I even don't know much about the exact alrogithm behind ECM, but I know how to use this program.

Perhaps it's general people asking others first than searching by themselves!
kar_bon is offline   Reply With Quote
Old 2010-07-26, 15:50   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by kar_bon View Post
I mean, before I use a program, I should know how to use it's parameters, read more about it from internet or this forum here, trying to learn about it, try others programs which do the same.

After this is all done, I would ask for help.
Sure, I even don't know much about the exact alrogithm behind ECM, but I know how to use this program.

Perhaps it's general people asking others first than searching by themselves!
For ECM one needs to know how the algorithm works before one can intelligently select its parameters.
R.D. Silverman is offline   Reply With Quote
Old 2010-07-26, 19:02   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2·5,573 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
For ECM one needs to know how the algorithm works before one can intelligently select its parameters.
I beg to differ. Someone who does not know how the algorithm works may be quite capable of interpreting advice provided by someone else who does have an in-depth understanding.


Paul
xilman is online now   Reply With Quote
Old 2010-07-26, 21:33   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by xilman View Post
I beg to differ. Someone who does not know how the algorithm works may be quite capable of interpreting advice provided by someone else who does have an in-depth understanding.


Paul
So we should all go through life in ignorance and merely accept answers
from others? And if someone (say) asks me and I give a deliberately
wrong answer, how will they know that it is wrong?

Math is an open subject. It can be read by anyone willing to take the
time to study it.

If you are interested in something you should take the time to learn how
it works.

Examples where people do not bother to learn for themselves readily
come to mind: The "Anti-Vaccination" kooks, the G-W deniers, and
other similar flat earthers.......
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Searching for Wagstaff PRP T.Rex Wagstaff PRP Search 191 2021-06-30 17:22
New Wagstaff PRP exponents ryanp Wagstaff PRP Search 26 2013-10-18 01:33
Hot tuna! -- a p75 and a p79 by Sam Wagstaff! Batalov GMP-ECM 9 2012-08-24 10:26
Wagstaff Conjecture davieddy Miscellaneous Math 209 2011-01-23 23:50
30th Wagstaff prime T.Rex Math 0 2007-09-04 07:10

All times are UTC. The time now is 12:31.


Thu Jan 27 12:31:23 UTC 2022 up 188 days, 7 hrs, 1 user, load averages: 1.80, 1.60, 1.47

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

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”