Fermat's factorization method (source code)

= Fermat's factorization method
{c}
{title2=$N=r^2-s^2$}
{wiki}

= Fermat factorization method
{c}
{synonym}

For a positive <odd integer> $N>1$, <Fermat's factorization method> searches for <integers> $r,s$ satisfying $N=r^2-s^2$. Start at $r=\lceil\sqrt N\rceil$ and test successive values until $r^2-N$ is a <perfect square> $s^2$. The <difference of two squares> then gives $N=(r-s)(r+s)$. For an even input, remove factors of two first.

For example, $N=5959$ starts at $r=78$. The differences $78^2-5959=125$ and $79^2-5959=282$ fail the <perfect square test>, whereas $80^2-5959=441=21^2$. Hence $5959=(80-21)(80+21)=59\cdot101$.

The search always reaches at least the trivial factor pair $(1,N)$, at $r=(N+1)/2$. It is useful when a nontrivial factor pair $u\leq v$ is close: that pair is reached at $r=(u+v)/2$, with
$$
r-\sqrt N=\frac{(\sqrt v-\sqrt u)^2}{2}.
$$
A small difference between factor sizes therefore requires few trials. This is a different advantage from looking for a small <prime factor> by <trial division>.