Re: Fermat's Factoring Method

From: mechmech (bbb_at_ccc.com)
Date: 02/19/05 

Date: Fri, 18 Feb 2005 19:02:42 -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 square for such
numbers can be contructed independently up to any size. 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. 

-- 
src="http://www.mozilla.org/sfx-images/affiliates/Buttons/88x31/get.gif"
"Bill Dubuque" <wgd@nestle.csail.mit.edu> wrote in message
news:y8zfyzxc369.fsf@nestle.csail.mit.edu...
> C. Bond <cbond@ix.netcom.com> wrote:
> >
> > Fermat's method reduces the problem of selecting trial
> > divisors by constraining the choices to perfect squares
> > instead of primes. Does anyone know how to estimate the
> > advantage for large N? Knuth explains the method and
> > some of its variants, but doesn't quantify the benefit.
>
> Perhaps of interest are the reviews in my prior post [1]
> esp. the paper by McKee: Speeding Fermat's factoring method.
>
> --Bill Dubuque
>
> [1] http://google.com/groups?selm=y8zzmyi51ye.fsf@nestle.csail.mit.edu
>     http://groups-beta.google.com/group/sci.math/msg/f2cec2810b56101c
Quantcast