 mersenneforum.org Best settings to factor Wagstaff p = (2^n +1) / 1
 Register FAQ Search Today's Posts Mark Forums Read 2010-07-26, 01:06 #1 diep   Sep 2006 The Netherlands 14168 Posts 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 Last fiddled with by diep on 2010-07-26 at 01:06   2010-07-26, 01:08 #2 kar_bon   Mar 2006 Germany 2×5×293 Posts 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   2010-07-26, 01:14   #3
diep

Sep 2006
The Netherlands

30E16 Posts Quote:
 Originally Posted by kar_bon 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
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\>   2010-07-26, 01:18   #4
kar_bon

Mar 2006
Germany

2×5×293 Posts Quote:
 Originally Posted by diep 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
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   2010-07-26, 01:26   #5
diep

Sep 2006
The Netherlands

11000011102 Posts Quote:
 Originally Posted by kar_bon 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
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
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
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
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
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>   2010-07-26, 06:48 #6 10metreh   Nov 2008 2×33×43 Posts 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 switch. Last fiddled with by 10metreh on 2010-07-26 at 06:48   2010-07-26, 13:47   #7
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by kar_bon 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.   2010-07-26, 14:24   #8
kar_bon

Mar 2006
Germany

1011011100102 Posts Quote:
 Originally Posted by R.D. Silverman 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!   2010-07-26, 15:50   #9
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by kar_bon 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.   2010-07-26, 19:02   #10
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·5,573 Posts Quote:
 Originally Posted by R.D. Silverman 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   2010-07-26, 21:33   #11
R.D. Silverman

Nov 2003

746010 Posts Quote:
 Originally Posted by xilman 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.......  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post T.Rex Wagstaff PRP Search 191 2021-06-30 17:22 ryanp Wagstaff PRP Search 26 2013-10-18 01:33 Batalov GMP-ECM 9 2012-08-24 10:26 davieddy Miscellaneous Math 209 2011-01-23 23:50 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