Fermat Factorization

Proposition. Let $n$ be a positive odd integer. There is a one-to-one correspondence between factorizations of $n$ in the form $n=ab$ , where $a\geq b>0$, and the representations of $n$ in the form $t^2-s^2$, where $s$ and $t$ are nonnegative integers. The correspondence is given by the equation
$$t=\frac{a+b}{2},\ s=\frac{a-b}{2};\ a=t+s,\ b=t-s$$

Proof. Given $n=ab$, we can write
Conversely, given $n=t^2-s^2$, $n$ can be factored as $n=(t+s)(t-s)$.

If $n=ab$ with $a$ and $b$ close together, then $s=\frac{a-b}{2}$ is small, and so $t=\frac{a+b}{2}$ is slightly larger than $\sqrt{n}$. In that case, we can find $a$ and $b$ by trying all values of $t$ starting with $[\sqrt{n}]+1$, until we find one for which $t^2-n=s^2$ is a perfect square. This method is called the Fermat factorization.

Example. Factor $200819$.

Solution. $[\sqrt{200819}]+1=449$.
\begin{align*} 449^2-200819&=782,\ \mbox{not a perfact square}\\ 450^2-200819&=1681=41^2 \end{align*}
$$200819=450^2-41^2=(450+41)(450-41)=491\cdot 409$$

If $a$ and $b$ are not close together for $n=ab$, although the Fermat factorization method will eventually find $a$ and $b$, one will have to try a large number of $t=[\sqrt{n}]+1, [\sqrt{n}]+2,\cdots$. There is a generalization of Fermat factorization. Choose small $k$, successively set $t=[\sqrt{kn}]+1, [\sqrt{kn}]+2,\cdots$, etc. until we find a $t$ for which $t^2-kn=s^2$ is a perfect square. Then $(t+s)(t-s)=kn$ and a nontrivial common factor of $n$ can be found by calculating $(t+s,n)$.

Example. Factor 141467.

Solution. First we factor 141467 by simple Fermat factorization. Since $\sqrt{141467}\approx 376.1209911717239$, we successively try $t=377,378,\cdots$ until we find $t^2-141467$ is a perfect square. We find
$$141467=414^2-173^2=(414+173)(414-173)=587\cdot 241$$
Now, this time we factor 141467 by generalized Fermat factorization with $k=3$. We try $t=[\sqrt{3n}]+1=652, 653,\cdots$ and find
$$t^2-3n=655^2-3\cdot 141467=4624=68^2=s^2$$
$(t+s,n)=(723,141467)=241$ and so $141467=241\cdot 587$.

The following two propositions tell us that it is not a good idea to choose an even number for $k$ in generalized Fermat factorization.

Proposition. If $k=2$, or if $k$ is any integer divisible by 2 but not by 4, then we cannot factor a large odd $n$ using generalized Fermat factorization with this choice of $k$.

Proof. $n$ is an odd integer, so $n=2m+1$ for some $m\in\mathbb{Z}$. For $k=2$, $kn=4m+2\equiv 4\mod 4$. If $k$ is an integer divisible by 2 but not by 4, $k=2(2l+1)=4l+2$ for some $l\in\mathbb{Z}$ and $kn\equiv 2\mod 4$. $t^2-s^2=kn\equiv 2\mod 4$, but the difference of two squares cannot be 2 modulo 4. (Each of the integers $t$ and $s$ is one of the forms $4u$, $4u+1$, $4u+2$, or $4u+3$ for some $u\in\mathbb{Z}$, so there are 16 different cases of $t$ and $s$ and in each case you can easily check if $t^2-s^2$ can be 2 modulo 4. For instance if $t=4u_1+1$ and $s=4u_2+2$, then
$t^2-s^2\equiv 1^2-2^2\equiv 1\mod 4$.)

Proposition. If $k=4$, and if generalized Fermat factorization works for a certain $t$, then simple Fermat factorization (with $k=1$) would have worked equally well.

Proof. $t^2-s^2=kn=4n\equiv 4\mod 8$ which can hold only if both $s$ and $t$ are even. In that case, $\left(\frac{s}{2}\right)^2=\left(\frac{t}{2}\right)^2-n$, so simple Fermat factorization would have worked equally well.

Leave a Reply

Your email address will not be published. Required fields are marked *