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
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.
That procedure first finds the factorization with the least values of a and b.
, so the number of steps is approximately
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
are squares: It is not necessary to compute all the square-roots of
The values repeat with each increase of a by 10.
produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values.
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.