Re: Critiquing surrogate factoring

From: Paul Leyland (paul_at_leyland.vispa.com)
Date: 03/30/05 

Date: 30 Mar 2005 20:45:51 +0100

"Pubkeybreaker" <Robert_silverman@raytheon.com> writes:

> Actually, No.
>
> Fermat's method factors N directly by representing it exactly as the
> difference of two squares. N = x^2 - y^2.

Yes and no.

There is excellent evidence to suggest that Fermat tried to factor N
on occasion by representing kN as the difference of two squares. I
remember some 30 years ago seeing an example he factored with k=8 (and
succeeded because N=p*q where q \approx 2*q) but can't lay my hands on
it at the moment. He astounded his contempories with this particular
feat.

Lehman, of course, showed how efficiently to factor N=p*q where p/q is
close to a simple ratio long after Fermat's day but using, in essence,
Fermat's idea.

Paul 

-- 
Hanging on in quiet desperation is the English way.  The time is gone,
the song is over.  Thought I'd something more to say.