Re: A very fast Fermat factoring algorithm

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

Date: 30 Mar 2005 20:48:20 -0800

I am well aware that a 10^9 speedup to Fermat's algorithm isn't going
to solve any RSA numbers overnight, but I was wondering if it was
anything new. I have read that the double large prime multiple
polynomial quadratic sieve (PPMPQS) uses Shanks' SQUFOF algorithm to
factor numbers in an intermediate step, and that SQUFOF replaced a
previous implimentation which used Fermat's algorithm. Since I can't
find an explanation of SQUFOF, and I don't fully understand the
explanation of PPMPQS, I thought someone else might know a way to apply
a high-speed Fermat algorithm. If, hypothetically, repeated Fermat
factorizations were the bottleneck of the PPMPQS algorithm, then indeed
a faster Fermat algorithm would have an application. If it isn't, I
was wondering if it had any academic value (i.e. publishable).

Now, it turns out that the quadratic residue technique for calculating
exclusion moduli technique IS equivalent to the exclusion moduli
technique that I was doing (though it isn't obvious why and I'll have
to figure that out). This accounts for 10^3 of the total speedup that
I've made. The remaining 10^6, a space/time tradeoff which I have not
found duplicated anywhere. Does anyone know of a way to make a
space/time tradeoff with Fermat's algorithm, and could explain it or
referenece it? If so, I'm prepared to share my algorithm because this
would mean that I haven't discovered anything new.

Thanks again for the help.

Relevant Pages

  • Re: revised quadratic.fs
    ... How is it possible to add code to your algorithm, ... arbitrary code to a slow algorithm results in a 3 - 10 times speedup. ... Although flocals are fast, they will make ...
    (comp.lang.forth)
  • Re: ISE 10.0 finally with multi-threading and SV support ?
    ... first parallel release improved runtimes by 5% or so, ... Amdahl's law - if you perfectly parallelize 25% of your algorithm (eg ... (ie, a 2.3x speedup). ... now are choosing lower clock speeds and increasing the number of cores ...
    (comp.arch.fpga)
  • Re: A very fast Fermat factoring algorithm
    ... > Another is a very old technique that uses exclusion moduli to ... I'd rather not share the technique just yet. ... I have heard of several Fermat speedups, but none that are nearly this ... nothing like Fermat's algorithm, but it has the same runtime ...
    (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)