Why Fermat method of factoring is as fast as it is.
- 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
z = A^2 + 2 f A - [ 2 f A + A^2 - z ], where [ 2 f A + A^2 - z] is the
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@... >