> 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.
Yes, of the form n*p+1 (not 2*n*p+1 :). This is for the simple reason
that every power of a prime <=k must divide Q (due to your definition
of how Q is produced). Then by the fundemental theorem of arithmetic,
(all numbers are able to be evenly divided into primes < themselves),
we know that any number <k must be a product of powers of primes <k,
and hence divide Q.
This is (unfortunatly) not useful for you, if your goal is to
deterministically find factors less than a certain limit. P-1 would
be much slower than trial division if that is your goal. P-1 is
useful for finding very large factors that would be missed by trial
division.
Oop, just got your other letter:
> 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?
It's only "sort of" more efficient than trial factoring. It will find
(some) large factors more quickly than trial factoring will, but it
wouldn't find the factor 2^40*p+1, which (unless p is very small) would
be found very easily by trial factoring.
> 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.
Why would you have trial factoring with such low bounds, but P-1 with
such high bounds? Just asking...
-Lucas
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
