20100726, 01:06  #1 
Sep 2006
The Netherlands
2×17×23 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 GMPECM 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 GMPECM 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 GMPECM 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 GMPECM 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 GMPECM 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 GMPECM 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... Last fiddled with by diep on 20100726 at 01:06 
20100726, 01:08  #2 
Mar 2006
Germany
2^{3}·3^{2}·41 Posts 
Try a smaller B1 like
Code:
echo {(2^^^^151 + 1) / 3}  ecm 100000 Last fiddled with by kar_bon on 20100726 at 01:09 
20100726, 01:14  #3  
Sep 2006
The Netherlands
782_{10} Posts 
Quote:
C:\factor\ecm>echo {(2^^^^151 + 1) / 3}  ecm 10000 GMPECM 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\> 

20100726, 01:18  #4  
Mar 2006
Germany
2^{3}·3^{2}·41 Posts 
Quote:
Code:
E:\ecm>echo {(2^^^^151 + 1) / 3}  ecm 10000 GMPECM 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 Do you know something more about the ECMalgorithm? Read first more about it, like using the B1param! Last fiddled with by kar_bon on 20100726 at 01:19 

20100726, 01:26  #5  
Sep 2006
The Netherlands
2×17×23 Posts 
Quote:
C:\factor\ecm>echo {(2^^^^151 + 1) / 3}  ecm 1000 GMPECM 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 GMPECM 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 GMPECM 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 GMPECM 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 GMPECM 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> 

20100726, 06:48  #6 
Nov 2008
2·3^{3}·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 <number_of_curves> switch. Last fiddled with by 10metreh on 20100726 at 06:48 
20100726, 13:47  #7 
Nov 2003
2^{2}×5×373 Posts 

20100726, 14:24  #8  
Mar 2006
Germany
2^{3}×3^{2}×41 Posts 
Quote:
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! 

20100726, 15:50  #9  
Nov 2003
1110100100100_{2} Posts 
Quote:


20100726, 19:02  #10  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
10110000110111_{2} Posts 
Quote:
Paul 

20100726, 21:33  #11  
Nov 2003
1110100100100_{2} Posts 
Quote:
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 "AntiVaccination" kooks, the GW deniers, and other similar flat earthers....... 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Searching for Wagstaff PRP  T.Rex  Wagstaff PRP Search  191  20210630 17:22 
New Wagstaff PRP exponents  ryanp  Wagstaff PRP Search  26  20131018 01:33 
Hot tuna!  a p75 and a p79 by Sam Wagstaff!  Batalov  GMPECM  9  20120824 10:26 
Wagstaff Conjecture  davieddy  Miscellaneous Math  209  20110123 23:50 
30th Wagstaff prime  T.Rex  Math  0  20070904 07:10 