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

Title	Fermat method
Canonical name	FermatMethod
Date of creation	2013-03-22 16:39:03
Last modified on	2013-03-22 16:39:03
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	6
Author	PrimeFan (13766)
Entry type	Algorithm
Classification	msc 11A41
Synonym	Fermat’s method
Synonym	Fermat factorization method
Synonym	Fermat’s factorization method