[EMAIL PROTECTED] writes:
> 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.
Gack. Yes, I should have caught that myself; it's the same situation
as for p, isn't it?
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.
Of course; I realize that. I was only looking at it this odd way
because of the trial factoring gaps I need to close. Since I already
have the P-1 data, it's easy to do this. If I didn't already have the
P-1 data, it would (most likely) be faster to simply do the trial
factoring.
Further, it seems to me that doing trial factoring to extend from P-1
factoring doesn't make sense. Note that trial factoring would have to
check 2*(k + 1)*p + 1 next; P-1 only has to do k + 1 next if it's a
prime or prime power (or p). Trial factoring could use the knowledge
of P-1 being done thru a stage one of k by "sieving" the trial factors
based on one less than the trial factors as well as the usual sieving
of the trial factors themselves, but that's exactly the set that P-1
would test with larger stage one bounds, and P-1 would, as you point
out, find more factors with at most a little extra work. Right?
I've heard that P-1 is "more efficient" than trial factoring; does the
proof go along these lines? Or is it more complicated than this?
Of course, if this is correct, then I should fill the trial factoring
gaps using P-1, at least to the largest stage one the program that I
use supports.
> 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.
So a composite p should effectively be treated as if it were prime in
the powering even though it's prime factors are being used as well?
That certainly makes sense, given the extra power of 2 and of p used
because of the special form of Mersenne factors.
Thanks,
Will
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
