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

[diep]

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...

[kar_bon]

Try a smaller B1 like

echo {(2^^^^151 + 1) / 3} | ecm 100000

Even B1=10000 can do it!

[diep]

Originally Posted by kar_bon

Try a smaller B1 like

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\>

[kar_bon]

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!

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!

[diep]

Originally Posted by kar_bon

Yes!

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>

[10metreh]

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.

[R.D. Silverman]

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.

[kar_bon]

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!

[R.D. Silverman]

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.

[xilman]

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

[R.D. Silverman]

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.......