Re: A very fast Fermat factoring algorithm

From: quantumgecko (pete2498_at_umn.edu)
Date: 03/30/05 

Date: 30 Mar 2005 08:44:06 -0800

Pubkeybreaker wrote:
> In fact, there are a several known techniques to speed Fermat
> factoring.
>
> 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.

I'd rather not share the technique just yet. I don't know for sure if
it has any value. I will say though that about ~10^6 of my speed up is
a space/time trade-off and about ~10^3 of it is an "exclusion moduli"
thing, although mine doesn't use quadratic residues. I'll have to
check, it's possible it's the same technique in disguise.

I have heard of several Fermat speedups, but none that are nearly this
fast. I also know of no method of space/time trade-off for Fermat's
algorithm besides this.

What I mean by "equivalent to Fermat's" is that it looks absolutely
nothing like Fermat's algorithm, but it has the same runtime
expression: # iterations = c(sqrt[p]-sqrt[q])^2 except that c=0.5 for
Fermat and c=10^-9 for me. I think the iterations are faster too.

I compared my algorithm to Pollard rho for my paper. Pollard rho
searches small factors fast, my algorithm searches big factors fast, so
this was an interesting test of usefulness. My algorithm beats Pollard
Rho on numbers from 15 to 40 decimal digits when 0.1 < p/q < 10, that
is, when the two primes have about the same number of decimal digits.
Other Fermat-like algorithms are much more strict about the closeness
of p and q.

Thank you for your comments.

Relevant Pages

  • Re: A very fast Fermat factoring algorithm
    ... there is a way to speed up Fermat's method by considering only the squares ... there are a several known techniques to speed Fermat ... > I'd rather not share the technique just yet. ... > nothing like Fermat's algorithm, but it has the same runtime ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • 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: Large-numbers division way too slow -- what to do?
    ... > This is barrett reduction ... This is close to the technique in Paul Barett's Crypto '86 ... easier to implement than Knuth's algorithm D. ... implementation of RSA escapes me. ...
    (sci.crypt)
  • Re: JSH: Binary quadratic Diophantines
    ... The first step of your algorithm ... Now I remember learning this technique in high school so *in ... these false statements, and sorry, but calling you on b.s. ... can CHECK me on that simply by reading my original post. ...
    (sci.physics)