Fermat's factorization method

For Fermat's method on determining extreme values, see Interior extremum theorem.

Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:

$N=a^{2}-b^{2}.$

That difference is algebraically factorable as $(a+b)(a-b)$; if neither factor equals one, it is a proper factorization of N.

Every odd number can be represented as such. If $N=cd$ is a factorization of N, then: $N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{2}$.

Since N is odd, both c and d are also odd, and hence the two terms in parentheses are integers.

In its simplest form, Fermat's method can be even slower than trial division (in the worst case). Nonetheless, combining Fermat's method and trial division can be more efficient than either method alone.