Hi folks
> Thanks for the "p-1 for dummies" e-mail.
> But as everyone on this list knows, any factor of a Mersenne
> number looks like 2*k*p+1 for N=2^p-1. Plugging this into
> the above equation gives
> q=2*k*p+1
> q-1=2*k*p
> Doesn't this mean the lower bound on a "p-1" method search should
> be greater that the Mersenne exponent (the p in 2^p-1) to have the best
> chance of success? Then the "upper bound" of the "p-1" search can
> be resevered for cracking a big factor in the "k" of a Mersenne factor.
This is a great point, one that I stopped a little way short on. Indeed the
'p-1' method constructs a large product of small primes, that you're hoping
will be a multiple of q-1. Since we know q-1 is a multiple of 2p, it makes
sense for us to start the p-1 method not at some base a, but at a^(2p). And
as you point out, the upper bound then is in fact an upper bound on the
factors of k. Provided we search as far as the factors of the unknown k, we
will succeed.
Starting at a^(2p) is relatively a small calculation, and saves us having to
wait until the P-1 method includes p in the exponentiation (it's highly
unlikely we would discover one before). Of course, its possible that even
so, we may not find a factor, but it makes sense to include as much as we
know about the factors at the very start of the method. Alternatively, we
could specify p as a lower bound - something which is probably a good idea
anyway, the calculation of a P-1 factoring is then comparable to a primality
test.
Going to a P-1 limit of 'p' certainly covers all factors with k<=p, and many
others besides. The factors that aren't covered are those with a prime or
prime power factor of k above the P-1 limit. That can help you make a good
guess as to how efficient your factoring attempt has been, of course, do not
forget it is also possible to save the result of a P-1 attempt, return
later, and "exponentiate some more" to increase the upper bound.
Chris
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
