## 5029RE: [PrimeNumbers] Re: Fermat Factoring with First Digits

Expand Messages
• Feb 1, 2002
> > In this case he was suggesting how to make the
> > 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

To be even more fair to Fermat, it's a pretty good algorithm if you know
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.

Paul
• Show all 11 messages in this topic