## Why Fermat method of factoring is as fast as it is.

Expand Messages
• Consider factoring of 91 = 10^2 - 3^2 = (10 - 3) * (10 + 3) This took one step by Fermat method whereas the difference of the factors is 13 - 7 = 6. I wondered
Message 1 of 1 , Nov 12, 2006
Consider factoring of 91 = 10^2 - 3^2 = (10 - 3) * (10 + 3)

This took one step by Fermat method whereas the difference of the
factors is 13 - 7 = 6.

I wondered why the Fermat method is actually much faster than
proportional to the difference of the factors.

Today I figured it out.

Let z = x y = t^2 - s^2

x = t - s; y = t + s; t = (y + x)/2 ; s = (y - x)/2

Let A = integer part of sqrt of z.

Assume z is not = to A^2 for otherwise the factoring is trivial.

x < A < y

Define f by

f = [ (y - A) - (A - x) ] / 2 = ( y - A - A + x)/2 = (2 t - 2 A )/2
= t - A

t = f + A

Note that f is defined to be half of the difference of the distance of
A from y and distance of A from x.

Since A is between x and y, f is significantly smaller than (y - x).

Note also that f is in lockstep with t.

z = t^2 - s^2 = (A + f)^2 - s^2 = A^2 + 2 f A + f^2 - s^2

Thus s^2 = A^2 + 2 f A + f^2 - z

Also
z = A^2 + 2 f A - [ 2 f A + A^2 - z ], where [ 2 f A + A^2 - z] is the
constant term.

Consider z to be a quadratic in A

A^2 + 2 f A - [2 f A + A^2 - z] factors as

[ A - ( -f - sqrt[ f^2 + 2 f A+ A^2 - z ] ) ] ) ] [ A - ( - f +
sqrt[ f^2 + 2 f A + A^2 - z ] )

= [ A - (-f - s) ] [ A - ( -f + s ) ]

= ( A + f - s) ( A+f - s)

which we could have figured out more quickly by

z = (t - s) * (t + s) = (A + f - s) * (A + f + s)

Thus, the Fermat method is acutally progressing by incrementing f by 1
, starting with f = 1, until f is half the difference
of the distances of A from x and distance of y from A.

This number , f, is significantly smaller than the distance (y - x).

If we could make a better initial guess than sqrt(z) for the value of t
= ( y + x) / 2, then we could find the factors more quickly.

Knowing lower bounds for x or upper bounds for y would enable us to put
stricter bounds on t.

Kermit < kermit@... >
Your message has been successfully submitted and would be delivered to recipients shortly.