Re: A very fast Fermat factoring algorithm

From: Pubkeybreaker (Robert_silverman_at_raytheon.com)
Date: 03/30/05 

Date: 30 Mar 2005 07:10:59 -0800

In fact, there are a several known techniques to speed Fermat
factoring.
One such is Sherman Lehman's technique that changes the algorithm from
O(sqrt(N)) to O(cuberoot(N)) via the use of weights that run through
Farey
sequences. This gives much more than just a constant time improvement
and it still just a Fermat variant.

Another is a very old technique that uses exclusion moduli to restrict
the
search space. If we have x^2 - y^2 = N, then x is a quad. res. One
can look at
N mod various primes. Then x modulo those primes must be a quad. res.

This can sharply reduce the values of x that must be searched. This
technique is
quite old (I know it was implemented by Lehmer back in the 30's when
he built
his photo-electric mechanical sieve; later implemented on his
delay-line sieves)

Please tell us what technique you are proposing.

Relevant Pages

  • Re: As the Crow flies.
    ... It means the product of the first, second and third primes. ... That is a feature of Legendre's technique. ... so, sieving is still a practical algorithm: it runs very fast, since it ... reasonable implementation of standard techniques. ...
    (talk.origins)
  • Re: a problem in elementary number theory
    ... this technique can be applied on the test. ... So, I know the only primes I need to examines are 2, 3 and 5. ... Arguing as in my other threads, Fermat's Little Theorem and an observation of the even factors conclude the answer must be divisible ... The extra factor of 2 cannot come from p-1 or p+1 because exactly one of them is a multiple of 4. ...
    (sci.math)
  • Re: As the Crow flies.
    ... Which is how many my algorithm took. ... be silly indeed to use Lehmer's algorithm to count primes up to 997. ... that's a meaningless endorsement of your technique. ...
    (talk.origins)
  • Re: As the Crow flies.
    ... Which is how many my algorithm took. ... be silly indeed to use Lehmer's algorithm to count primes up to 997. ... that's a meaningless endorsement of your technique. ...
    (talk.origins)