> From: Brian J. Beesley [mailto:[EMAIL PROTECTED]]
> If P-1 does find a factor which is compound, then running P-1 again
> with smaller limits will eventually recover a smaller factor. These
> extra runs will obviously take less time than the original
Indeed, and with care one can usually choose the bounds so only one more run
is necessary. Factoring c-1 (where c is the composite factor found) and
judiciously chosing which primes to omit is the method. This factorization
is extremely easy, because of the way in which c was discovered. In
practice, discarding the prime factor of c found in stage 2 is all that's
usually needed. If c was found after stage 1, and so there is no large
prime, discarding half (rounded up if the number is odd) of the powers of 2
usually does the trick.
Of course, all these computations are performed on c, and not the original
integer.
It's a pity that a similar procedure isn't known for ECM, or at least not
known to me.
Paul
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
