Fermat's Factorization Method

Given a number $n$, look for Integers $x$ and $y$ such that $n=x^2-y^2$. Then

$$n=(x-y)(x+y)$$ (1)

and $n$ is factored. Any Odd Number can be represented in this form since then $n=ab$, $a$ and $b$ are Odd, and

$$a = x+y$$ (2)

$$b = x-y.$$ (3)

Adding and subtracting,

$$a+b = 2x$$ (4)

$$a-b = 2y,$$ (5)

so solving for $x$ and $y$ gives

$$x = {\textstyle{1\over 2}}(a+b)$$ (6)

$$y = {\textstyle{1\over 2}}(a-b).$$ (7)

Therefore,

$$x^2-y^2={\textstyle{1\over 4}}[(a+b)^2-(a-b)^2] = ab.$$ (8)

As the first trial for $x$, try $x_1\left\lceil{\sqrt{n}\,}\right\rceil$, where $\left\lceil{x}\right\rceil$ is the Ceiling Function. Then check if

$$\Delta x_1 ={x_1}^2-n$$ (9)

is a Square Number. There are only 22 combinations of the last two digits which a Square Number can assume, so most combinations can be eliminated. If $\Delta x_1$ is not a Square Number, then try

$$x_2=x_1+1,$$ (10)

so

$$\Delta x_2 = {x_2}^2-n=(x_1+1)^2-n={x_1}^2+2x_1+1-n$$

$$= \Delta x_1+2x_1+1.$$ (11)

Continue with

$$\Delta x_3 = {x_3}^2-n=(x_2+1)^2-n={x_2}^2+2x_2+1-n$$

$$= \Delta x_2+2x_2+1=\Delta x_2+2x_1+3,$$ (12)

so subsequent differences are obtained simply by adding two.

Maurice Kraitchik sped up the Algorithm by looking for $x$ and $y$ satisfying

$$x^2\equiv y^2\ \left({{\rm mod\ } {n}}\right),$$ (13)

i.e., $n\vert(x^2-y^2)$. This congruence has uninteresting solutions $x\equiv \pm y\ \left({{\rm mod\ } {n}}\right)$ and interesting solutions $x\not\equiv \pm y {\rm\ (mod}\ n)$. It turns out that if $n$ is Odd and Divisible by at least two different Primes, then at least half of the solutions to $x^2\equiv y^2\ \left({{\rm mod\ } {n}}\right)$ with $xy$ Coprime to $n$ are interesting. For such solutions, $(n,x-y)$ is neither $n$ nor 1 and is therefore a nontrivial factor of $n$ (Pomerance 1996). This Algorithm can be used to prove primality, but is not practical. In 1931, Lehmer and Powers discovered how to search for such pairs using Continued Fractions. This method was improved by Morrison and Brillhart (1975) into the Continued Fraction Factorization Algorithm, which was the fastest Algorithm in use before the Quadratic Sieve Factorization Method was developed.

See also Prime Factorization Algorithms, Smooth Number

References

Lehmer, D. H. and Powers, R. E. ``On Factoring Large Numbers.'' Bull. Amer. Math. Soc. 37, 770-776, 1931.

Morrison, M. A. and Brillhart, J. ``A Method of Factoring and the Factorization of $F_7$.'' Math. Comput. 29, 183-205, 1975.

Pomerance, C. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.