Fermat method

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. 1.

Initialize the iterator $i=\lceil\sqrt{n}\rceil$ and test cap at $\sqrt{i^{2}-n}$.

2. 2.

Compute $j=\sqrt{i^{2}-n}$.

3. 3.

Test if $j$ is an integer. If it is, break out of subroutine and return $i-j$.

4. 4.

Increment iterator $i$ once. If $i<\frac{n+9}{6}$, go to step 2.

5. 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.

References

• 1 R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.1
Title Fermat method FermatMethod 2013-03-22 16:39:03 2013-03-22 16:39:03 PrimeFan (13766) PrimeFan (13766) 6 PrimeFan (13766) Algorithm msc 11A41 Fermat’s method Fermat factorization method Fermat’s factorization method