Hi,
First off, thanks to all that have submitted ideas to my
factoring challenge. A few have even started to write the assembly code.
I hope to incorporate these ideas and code sometime next year.
Secondly, I must apologize for not reviewing and commenting on the
suggestions. I have saved them all for a thorough review at a later date.
However, Mayer's idea got me thinking...
At 05:12 PM 11/26/98 +0100, Mayer wrote something to the effect of:
>Prove that P-1 factoring won't be better than more sieving.
I wrote a program to analyze P-1 factoring success rate.
I assumed that GCDs are free (they certainly aren't) and
that factors longer than 87-bits won't change the calculations much.
Basically, P-1 succeeds if the k in the factor of the form 2kp+1
is smooth, that is, k has no large factors. My program samples
a 1000 values of k to compute a success rate:
A sample run:
Analysis of p=10000019, how_far_factored=64, B1=20000, B2=200000
65-bit factors: 8.5% in pass 1, 18.3% in pass 2
66-bit factors: 7.8% in pass 1, 16.6% in pass 2
67-bit factors: 6.6% in pass 1, 14.8% in pass 2
68-bit factors: 5.7% in pass 1, 13.4% in pass 2
69-bit factors: 4.7% in pass 1, 11.7% in pass 2
70-bit factors: 3.6% in pass 1, 9% in pass 2
71-bit factors: 4% in pass 1, 9.4% in pass 2
72-bit factors: 3.3% in pass 1, 8.4% in pass 2
73-bit factors: 1.7% in pass 1, 5.9% in pass 2
74-bit factors: 1.4% in pass 1, 5.2% in pass 2
75-bit factors: 1.1% in pass 1, 4% in pass 2
76-bit factors: 0.9% in pass 1, 3.7% in pass 2
77-bit factors: 1% in pass 1, 3.3% in pass 2
78-bit factors: 0.8% in pass 1, 3% in pass 2
79-bit factors: 1% in pass 1, 2.9% in pass 2
80-bit factors: 0.6% in pass 1, 2.9% in pass 2
81-bit factors: 0.7% in pass 1, 2.7% in pass 2
82-bit factors: 0.4% in pass 1, 1.5% in pass 2
83-bit factors: 0.5% in pass 1, 1.8% in pass 2
84-bit factors: 0.3% in pass 1, 1.2% in pass 2
85-bit factors: 0.2% in pass 1, 2% in pass 2
86-bit factors: 0.2% in pass 1, 1.3% in pass 2
87-bit factors: 0.4% in pass 1, 1.1% in pass 2
Pass 1 squarings: 28820 or 0.2882%
Pass 2 squarings: 15722 or 0.15722%
Total probability of finding a factor: 2.04448%
That is, P-1 will cover 18.3% of the 65-bit factors (a .183/65 chance
that a 65-bit factor will be found).
And for a cost of 44542 squarings (or .445% of a LL test)
you will eliminate 2.04% of the LL candidates. A winner!!
So the questions are now 1) What are the optimal values for B1
and B2? and 2) Will sieving find more factors in less time than
P-1 factoring?
The code is available at http://www.magicnet.net/~woltman/pminus1.cpp
for those that want to play with it.
Some other runs:
Analysis of p=10000019, how_far_factored=64, B1=20000, B2=400000
Pass 1 squarings: 28820 or 0.2882%
Pass 2 squarings: 31598 or 0.315979%
Total probability of finding a factor: 2.46762%
Analysis of p=10000019, how_far_factored=64, B1=20000, B2=800000
Pass 1 squarings: 28820 or 0.2882%
Pass 2 squarings: 61689 or 0.616889%
Total probability of finding a factor: 2.90801%
Analysis of p=10000019, how_far_factored=64, B1=50000, B2=500000
Pass 1 squarings: 72114.5 or 0.721144%
Pass 2 squarings: 36405 or 0.364049%
Total probability of finding a factor: 3.0994%
Analysis of p=10000019, how_far_factored=64, B1=50000, B2=1000000
Pass 1 squarings: 72114.5 or 0.721144%
Pass 2 squarings: 73365 or 0.733649%
Total probability of finding a factor: 3.68311%
Analysis of p=10000019, how_far_factored=64, B1=50000, B2=2000000
Pass 1 squarings: 72114.5 or 0.721144%
Pass 2 squarings: 143800 or 1.438%
Total probability of finding a factor: 4.26091%
Analysis of p=10000019, how_far_factored=64, B1=100000, B2=2000000
Pass 1 squarings: 144344 or 1.44344%
Pass 2 squarings: 139341 or 1.39341%
Total probability of finding a factor: 4.70716%
Analysis of p=10000019, how_far_factored=64, B1=100000, B2=4000000
Pass 1 squarings: 144344 or 1.44344%
Pass 2 squarings: 273554 or 2.73553%
Total probability of finding a factor: 5.35872%
Analysis of p=10000019, how_far_factored=64, B1=100000, B2=8000000
Pass 1 squarings: 144344 or 1.44344%
Pass 2 squarings: 530185 or 5.30184%
Total probability of finding a factor: 5.9836%
