Re: A very fast Fermat factoring algorithm

From: mechmech (bbb_at_ccc.com)
Date: 03/30/05 

Date: Wed, 30 Mar 2005 12:22:43 -0500

there is a way to speed up Fermat's method by considering only the squares
that enter in the factorization
of numbers of the form N=p*q where p and q are primes. The squares for such
numbers can be contructed independently up to any size in a matrix. Of
course the
original problem of finding the right squares for a given N is still there
but at least we do not have to consider squares that we know are not part of
the solution. 

-- 
mahfoud belhadj
(519) 579-9985
errifi@golden.net
"quantumgecko" <pete2498@umn.edu> wrote in message
news:1112201046.931941.197210@z14g2000cwz.googlegroups.com...
> 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
    ... > 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: Counting knight moves
    ... All of those squares are two moves from a6; ... I'm pretty sure you said that Alexander's Technique was taking you ten ... You opponent has a knight on g1. ... something which I can already do and feel that any chess player beyond ...
    (rec.games.chess.misc)
  • Re: Counting knight moves
    ... knight can't even move from b3 to a4. ... the two squares. ... I'd rather stick to discussing the technique than starting to talk ... That's not criticism of the technique. ...
    (rec.games.chess.misc)
  • Re: Not complicated, weird situation
    ... of squares in some way that involves factoring a number you get to ... This is a faaaaantastic algorithm. ... > better than 50% success rate, which is a claim you made but didn't ... > hard work, Harris' work broke into society with the help of Justin, ...
    (sci.crypt)
  • Re: Help with Class
    ... figure the sizes to cut squares for their own blocks, ... made in each technique: eg,. all flying geese, all Card Tricks; ... Card tricks is entirely different, as is the Duck and Ducklings; ... Session 2 date Nifty Nines - Speed piecing scrappy nine-patches ...
    (rec.crafts.textiles.quilting)