Fermat's factorization method
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd numbers|odd] integer as the difference of two squares:
That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N.
Each odd number has such a representation. Indeed, if is a factorization of N, then
Since N is odd, then c and d are also odd, so those halves are integers.
In its simplest form, Fermat's method might be even slower than trial division. Nonetheless, the combination of trial division and Fermat's is more effective than either by itself.
Basic method
One tries various values of a, hoping that, a square.FermatFactor: // N should be odd
a ←
b2 ← a*a - N
repeat until b2 is a square:
a ← a + 1
b2 ← a*a - N
// equivalently:
// b2 ← b2 + 2*a + 1
// a ← a + 1
return a - // or a +
For example, to factor, the first try for a is the square root of rounded up to the next integer, which is. Then. 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.
| Try: | 1 | 2 | 3 |
| a | 78 | 79 | 80 |
| b2 | 125 | 282 | 441 |
| b | 11.18 | 16.79 | 21 |
The third try produces the perfect square of 441. Thus,,, and the factors of are and.
Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is, is the smallest factor ≥ the square-root of N, and so is the largest factor ≤ root-N. If the procedure finds, that shows that N is prime.
For, let c be the largest subroot factor., so the number of steps is approximately.
If N is prime, one needs steps. This is a bad way to prove primality. But if N has a factor close to its square root, the method works quickly. More precisely, if c differs less than from, the method requires only one step; this is independent of the size of N.
Fermat's and trial division
Consider trying to factor the prime number, but also compute b and throughout. Going up from rounded up to the next integer, which is 48,433, we can tabulate:| Try | ||||
| a | 48,433 | 48,434 | 48,435 | 48,436 |
| b2 | 76,572 | 173,439 | 270,308 | 367,179 |
| b | 276.7 | 416.5 | 519.9 | 605.9 |
| a − b | 48,156.3 | 48,017.5 | 47,915.1 | 47,830.1 |
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, Fermat's method would have found it already.
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 ; use Fermat's method for factors between and. This gives a bound for trial division which is. In the above example, with the bound for trial division is 47830. A reasonable choice could be giving a bound of 28937.
In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
| a | 60,001 | 60,002 |
| b2 | 1,254,441,084 | 1,254,561,087 |
| b | 35,418.1 | 35,419.8 |
| a − b | 24,582.9 | 24,582.2 |
Sieve improvement
When considering the table for, one can quickly tell that none of the values of are squares:| a | 48,433 | 48,434 | 48,435 | 48,436 |
| b2 | 76,572 | 173,439 | 270,308 | 367,179 |
| b | 276.7 | 416.5 | 519.9 | 605.9 |
It is not necessary to compute all the square-roots of, nor even examine all the values for. Squares are always congruent to 0, 1, 4, 5, 9, 16 modulo 20, because these are the quadratic residues of 20. The values repeat with each increase of by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20, 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. Thus, must be 1 mod 20, which means that is 1, 9, 11 or 19 mod 20; it will produce a which ends in 4 mod 20 and, if square, will end in 2 or 8 mod 10.
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 and a modulus, one can proceed thus:
, astart, aend, astep, modulus)
a ← astart
do modulus times:
b2 ← a*a - N
if b2 is a square, modulo modulus:
, a, aend, astep * modulus, NextModulus)
endif
a ← a + astep
enddo
But the recursion is stopped when few a-values remain; that is, when / 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 is known, then a rational number can be picked near that value., and Fermat's method, applied to Nuv, will find the factors and quickly. Then and.
Generally, if the ratio is not known, various 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 time.