Fermat's factorization method

One tries various values of a, hoping that ${\displaystyle a^{2}-N=b^{2}}$ , a square.

FermatFactor(N): // N should be odd
    a ← ceiling(sqrt(N))
    b2 ← a*a - N
    repeat until b2 is a square:
        a ← a + 1
        b2 ← a*a - N 
     // equivalently: 
     // b2 ← b2 + 2*a + 1 
     // a ← a + 1
    return a - sqrt(b2) // or a + sqrt(b2)

For example, to factor ${\displaystyle N=5959}$ , the first try for a is the square root of 5959 rounded up to the next integer, which is 78. Then ${\displaystyle b^{2}=78^{2}-5959=125}$ . Since 125 is not a square, a second try is made by increasing the value of a by 1. The second attempt also fails, because 282 is again not a square.

The third try produces the perfect square of 441. Thus, ${\displaystyle a=80}$ , ${\displaystyle b=21}$ , and the factors of 5959 are ${\displaystyle a-b=59}$  and ${\displaystyle a+b=101}$ .

Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is, ${\displaystyle a+b}$  is the smallest factor ≥ the square-root of N, and so ${\displaystyle a-b=N/(a+b)}$  is the largest factor ≤ root-N. If the procedure finds ${\displaystyle N=1\cdot N}$ , that shows that N is prime.

For ${\displaystyle N=cd}$ , let c be the largest subroot factor. ${\displaystyle a=(c+d)/2}$ , so the number of steps is approximately ${\displaystyle (c+d)/2-{\sqrt {N}}=({\sqrt {d}}-{\sqrt {c}})^{2}/2=({\sqrt {N}}-c)^{2}/2c}$ .

If N is prime (so that ${\displaystyle c=1}$ ), one needs ${\displaystyle O(N)}$  steps. This is a bad way to prove primality. But if N has a factor close to its square root, the method works quickly. More precisely, if c differs less than ${\displaystyle {\left(4N\right)}^{1/4}}$  from ${\displaystyle {\sqrt {N}}}$ , the method requires only one step; this is independent of the size of N.^{[citation needed]}

Consider trying to factor the prime number N = 2,345,678,917, but also compute b and a − b throughout. Going up from ${\displaystyle {\sqrt {N}}}$  rounded up to the next integer, which is 48,433, we can tabulate:

In practice, one wouldn't bother with that last row until b is an integer. But observe that if N had a subroot factor above ${\displaystyle a-b=47830.1}$ , Fermat's method would have found it already.

Trial division would normally try up to 48,432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality.

This all suggests a combined factoring method. Choose some bound ${\displaystyle a_{\mathrm {max} }>{\sqrt {N}}}$ ; use Fermat's method for factors between ${\displaystyle {\sqrt {N}}}$  and ${\displaystyle a_{\mathrm {max} }}$ . This gives a bound for trial division which is ${\displaystyle a_{\mathrm {max} }-{\sqrt {a_{\mathrm {max} }^{2}-N}}}$ . In the above example, with ${\displaystyle a_{\mathrm {max} }=48436}$  the bound for trial division is 47830. A reasonable choice could be ${\displaystyle a_{\mathrm {max} }=55000}$  giving a bound of 28937.

In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:

When considering the table for ${\displaystyle N=2345678917}$ , one can quickly tell that none of the values of ${\displaystyle b^{2}}$  are squares:

It is not necessary to compute all the square-roots of ${\displaystyle a^{2}-N}$ , nor even examine all the values for a. Squares are always congruent to 0, 1, 4, 5, 9, 16 modulo 20. The values repeat with each increase of a by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), ${\displaystyle a^{2}-N}$  produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values. It is apparent that only the 4 from this list can be a square. Thus, ${\displaystyle a^{2}}$  must be 1 mod 20, which means that a is 1, 9, 11 or 19 mod 20; it will produce a ${\displaystyle b^{2}}$  which ends in 4 mod 20 and, if square, b will end in 2 or 8 mod 10.

This can be performed with any modulus. Using the same ${\displaystyle N=2345678917}$ ,

One generally chooses a power of a different prime for each modulus.

Given a sequence of a-values (start, end, and step) and a modulus, one can proceed thus:

FermatSieve(N, astart, aend, astep, modulus)
    a ← astart
    do modulus times:
        b2 ← a*a - N
        if b2 is a square, modulo modulus:
            FermatSieve(N, a, aend, astep * modulus, NextModulus)
        endif
        a ← a + astep
    enddo

But the recursion is stopped when few a-values remain; that is, when (aend-astart)/astep is small. Also, because a's step-size is constant, one can compute successive b2's with additions.

Fermat's method works best when there is a factor near the square-root of N.

If the approximate ratio of two factors (${\displaystyle d/c}$ ) is known, then a rational number ${\displaystyle v/u}$  can be picked near that value. ${\displaystyle Nuv=cv\cdot du}$ , and Fermat's method, applied to Nuv, will find the factors ${\displaystyle cv}$  and ${\displaystyle du}$  quickly. Then ${\displaystyle \gcd(N,cv)=c}$  and ${\displaystyle \gcd(N,du)=d}$ . (Unless c divides u or d divides v.)

Generally, if the ratio is not known, various ${\displaystyle u/v}$  values can be tried, and try to factor each resulting Nuv. R. Lehman devised a systematic way to do this, so that Fermat's plus trial division can factor N in ${\displaystyle O(N^{1/3})}$  time.^[1]

The fundamental ideas of Fermat's factorization method are the basis of the quadratic sieve and general number field sieve, the best-known algorithms for factoring large semiprimes, which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of ${\displaystyle a^{2}-n}$ , it finds a subset of elements of this sequence whose product is a square, and it does this in a highly efficient manner. The end result is the same: a difference of squares mod n that, if nontrivial, can be used to factor n.

• Completing the square
• Factorization of polynomials
• Factor theorem
• FOIL rule
• Monoid factorisation
• Pascal's triangle
• Prime factor
• Factorization
• Euler's factorization method
• Integer factorization
• Program synthesis
• Table of Gaussian integer factorizations
• Unique factorization

• Fermat (1894), Oeuvres de Fermat, vol. 2, p. 256
• McKee, J (1999). "Speeding Fermat's factoring method". Mathematics of Computation. 68 (228): 1729–1737. doi:10.1090/S0025-5718-99-01133-3.

• Fermat's factorization running time, at blogspot.in
• Fermat's Factorization Online Calculator, at windowspros.ru