Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Paul Leyland
    Feb 1, 2002
    • 0 Attachment
      > > 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