5029RE: [PrimeNumbers] Re: Fermat Factoring with First Digits
- Feb 1, 2002
> > In this case he was suggesting how to make theTo be even more fair to Fermat, it's a pretty good algorithm if you know
> > very slow Fermat method slightly less slow, I guess?
> Haha, to be honest, if you throw a few trivial improvements
> into Fermat, it's not too shabby on the just-over-word-size
that the composite has precisely two factors and that they differ only
slightly in size.
A case in point occurs in the 2-prime version of MPQS. Suppose a large
prime p lies in the range B1<p<B2 and a residue after dividing by factor
base primes (i.e all those <= B1) lies between max (B1^2, B2) and B2^2.
A fast pseudoprimality test tells us whether it's worth attempting to
factor the residue. In these circumstances, where B1 is typically
2^20and B2 is, say, 2^26 Fermat's method can be quite valuable.
I actually used Fermat for a while in PPMPQS, but we later found that
SQFOF almost always beat it.
- << Previous post in topic Next post in topic >>