Will Edgingtom writes:
> If I understand P-1 factoring correctly, then using it to a stage one
> bound of k to try to factor M(p) will find all possible factors less
> than or equal to 2*k*p + 1. I'm assuming that p is less than k (or p
> is always used in the powering) and the convention several of us
> agreed on a while back that all prime powers less than the stage one
> bound are used in the powering, not just the primes themselves. That
> is, trying to factor M(97), say, to a stage one bound of 10 would use
> 8, 9, 5, 7, and 97, not just 2, 3, 5, and 7.
Yes, p itself should be used in the powering.
So should all prime powers below (or up to and including) k.
> Am I correct? Or could a factor smaller than 2*k*p + 1 be missed in
> some cases?
In the last example a factor 16*97 + 1 could be missed.
Otherwise all factors below 2*k*p + 1 should be found.
One extra squaring will achieve the 2*k*p + 1 bound.
The power of the P-1 algorithm is that it can potentially find
many larger factors, such as 252*p +1 using a stage 1 bound of 10.
Observe 252 = 4 * 9 * 7 is a product of prime powers each <= 10.
If you want to check only for prime factors below 2*k*p + 1,
P-1 is not the way. [P-1 coupled with ECM might be the way if k is
large, although some uncertainty remains even after repeated ECM runs.]
> Does it matter whether p is prime or not? I don't think so, but ...
Not if you always include an exponentiation by p, and repeat it
if necessary as you do primes <= k.
Peter Montgomery
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
