Paul Leyland wrote:
> It's well known that factors of M(p) are of the form 2kp+1.
>
> When applying P-1 to mersenne numbers, an additional 2*p ought to be
> included in the product, over and above all the powers of prime < B1. Can
> anyone who knows for certain reassure me that this has been done for the
> prime95 V20 implementation?
Yes, thats a property of P-1 that makes it very well-suited for factoring
Mersennes. If the exponent is 10^x, you get x (+log_10(2) to be precise..)
digits in the factor for free. This is used in all P-1 implementations that I
am aware of.
And here's another little extra:
Factors are 1 or 7 (mod 8). Lets look at the 1 (mod 8) case:
2kp+1 = 1 (8)
2kp=0 (8)
kp=0 (4)
p is an odd prime => k is divisible by 4. Since the chance of the factor being
1 (8) seems to be 50%, 4 has a 50% chance of dividing k, 8 has a 25% chance,
etc, so on average, theres yet another 2! So you best start by exponentiating
your root by 4*p.
Considering the 7 (mod 8) case (I dont know the proof off my head) it turns out
that 3 has a 50% chance of dividing k, 5 has a 25% chance, 7 a 1/6 chance etc -
so the k is a little more smooth then you'd expect a random number to be.
I've been stuggling with modelling this into a formula that tells the chance of
finding a factor of a given size with P-1, given certain bounds, but I got lost
in cases that mutually exclude somewhere.. I have a little time now (exams
done! :) and try some more. Somehow I feel that, since the 1 or 7 (8) property
halves the number of factors to consider and P-1 seems to fully benefit from
this property through "extra smoothness", the difficulty of the task of
factoring k by P-1 should be reduced to factoring some number k/sqrt(2). That
would be interesting to (dis-)prove.
Ciao,
Alex.
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
