Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: That difference is algebraically factorable as
(A multiple of four is also a difference of squares: let c and d be even.)
In its simplest form, Fermat's method might be even slower than trial division (worst case).
Nonetheless, the combination of trial division and Fermat's is more effective than either by itself.
, the first try for a is the square root of 5959 rounded up to the next integer, which is 78.
Since 125 is not a square, a second try is made by increasing the value of a by 1.
The second attempt also fails, because 282 is again not a square.
That procedure first finds the factorization with the least values of a and b.
, let c be the largest subroot factor.
But if N has a factor close to its square root, the method works quickly.
, the method requires only one step; this is independent of the size of N.[citation needed] Consider trying to factor the prime number N = 2,345,678,917, but also compute b and a − b throughout.
rounded up to the next integer, which is 48,433, we can tabulate: In practice, one wouldn't bother with that last row until b is an integer.
Trial division would normally try up to 48,432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality.
This all suggests a combined factoring method.
This gives a bound for trial division which is
In this regard, Fermat's method gives diminishing returns.
One would surely stop before this point: When considering the table for
The values repeat with each increase of a by 10.
It is apparent that only the 4 from this list can be a square.
, One generally chooses a power of a different prime for each modulus.
Given a sequence of a-values (start, end, and step) and a modulus, one can proceed thus: But the recursion is stopped when few a-values remain; that is, when (aend-astart)/astep is small.
Also, because a's step-size is constant, one can compute successive b2's with additions.
Fermat's method works best when there is a factor near the square-root of N. If the approximate ratio of two factors (
, and Fermat's method, applied to Nuv, will find the factors
values can be tried, and try to factor each resulting Nuv.
R. Lehman devised a systematic way to do this, so that Fermat's plus trial division can factor N in
[1] The fundamental ideas of Fermat's factorization method are the basis of the quadratic sieve and general number field sieve, the best-known algorithms for factoring large semiprimes, which are the "worst-case".
The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of
, it finds a subset of elements of this sequence whose product is a square, and it does this in a highly efficient manner.
The end result is the same: a difference of squares mod n that, if nontrivial, can be used to factor n.