Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:
Contents
- Basic method
- Fermats and trial division
- Sieve improvement
- Multiplier improvement
- Other improvements
- References
That difference is algebraically factorable as
Each odd number has such a representation. Indeed, if
Since N is odd, then c and d are also odd, so those halves are integers. (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.
Basic method
One tries various values of a, hoping that
For example, to factor
The third try produces the perfect square of 441. So,
Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is,
For
If N is prime (so that
Fermat's and trial division
Consider trying to factor the prime number N = 2345678917, but also compute b and a − b throughout. Going up from
In practice, one wouldn't bother with that last row, until b is an integer. But observe that if N had a subroot factor above
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. Choose some bound
In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
Sieve improvement
It is not necessary to compute all the square-roots of
One can quickly tell that none of these values of
This can be performed with any modulus. Using the same
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:
FermatSieve(N, astart, aend, astep, modulus) a ← astart do modulus times: b2 ← a*a - N if b2 is a square, modulo modulus: FermatSieve(N, a, aend, astep * modulus, NextModulus) endif a ← a + astep enddoBut 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.
Multiplier improvement
Fermat's method works best when there is a factor near the square-root of N.
If the approximate ratio of two factors (
Generally, if the ratio is not known, various
Other improvements
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