The Fermat method is a factorization algorithm for odd integers that tries to represent them as the difference of two square numbers.

Call the Fermat method algorithm with an integer $n = 2x + 1$ .

1. Initialize the iterator $i = \lceil \sqrt{n} \rceil$ and test cap at $\sqrt{i^2 - n}$ .
2. Compute $j = \sqrt{i^2 - n}$ .
3. Test if $j$ is an integer. If it is, break out of subroutine and return $i - j$ .
4. Increment iterator $i$ once. If $i < \frac{n + 9}{6}$ , go to step 2.
5. Return $n$ .

For example, $n = 221$ . The square root is approximately 15, so that's what we set our iterator's initial state to. The test cap is 39.

At $i = 15$ , we find that $\sqrt{15^2 - 221} = 2$ , clearly an integer.

Then, $15 - 2 = 13$ and $15 + 2 = 17$ . By multiplication, we verify that $221 = 13 \cdot 17$ , indeed. By trial division, this would have taken 15 test divisions.

However, there are integers for which trial division performs much better than the Fermat method, such as numbers of the form $3p$ where $p$ is an odd prime greater than 3.

Bibliography

1

R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.1