## You are here

HomeFermat method

## Primary tabs

# 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 $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.

# References

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

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections