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=n and test cap at i2-n.

  2. 2.

    Compute j=i2-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<n+96, 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 152-221=2, clearly an integer.

Then, 15-2=13 and 15+2=17. By multiplicationPlanetmathPlanetmath, we verify that 221=1317, indeed. By trial divisionMathworldPlanetmath, 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 NumbersMathworldPlanetmath: A Computational Perspective, Springer, NY, 2001: 5.1
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