Fermat's factorization method

Fermat's factorization method is a representation of an odd integer as the difference of two squares:

${\displaystyle N=a^{2}-b^{2}.}$

That difference is algebraically factorable as ${\displaystyle (a+b)(a-b)}$; if neither factor equals one, it is a proper factorization of N. Put another way, we are looking for a,b such that a² ≡ b² (mod N), called a congruence of squares.

Each odd number has such a representation. Indeed, if ${\displaystyle N=cd}$ is a factorization of N, then

${\displaystyle N=[(c+d)/2]^{2}-[(c-d)/2]^{2}.}$

Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.)

In its simplest form, Fermat's method might be even slower than trial division (worst case). Even the combination of trial division and Fermat's method can be less effective than trial division.

The basic method

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

FermatFactor(N): // N should be odd

A ← ceil(sqrt(N))

Bsq ← A*A - N

while Bsq isn't a square:

A ← A + 1

Bsq ← A*A - N // equivalently: Bsq ← Bsq + 2*A - 1

endwhile

return A - sqrt(Bsq) // or A + sqrt(Bsq)

For example, to factor ${\displaystyle N=5959}$ , one computes

A:	78	79	80
Bsq:	125	282	441

The third try produces a square. ${\displaystyle A=80}$ , ${\displaystyle B=21}$ , and the factors are ${\displaystyle A-B=59}$ , and ${\displaystyle A+B=101}$ .

Suppose N has more than one factorization. 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*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. Note, that this is independant of the size of N.

Fermat's and trial division

Let's factor the prime number N=2345678917, but also compute B and A-B throughout.

A:	48433	48434	48435	48436
Bsq:	76572	173439	270308	367179
B:	276.7	416.5	519.9	605.9
A-B:	48156.3	48017.5	47915.1	47830.1

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 48432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality.

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

A:	60001	60002
Bsq:	1254441084	1254561087
B:	35418.1	35419.8
A-B:	24582.9	24582.2

This all suggests a combined factoring method. Choose some bound c; use trial division to find factors below c, and Fermat's for factors above c. That is, do Fermat until ${\displaystyle a-b<c}$ , or ${\displaystyle a>(c+N/c)/2}$ . The best choice of c depends on N, and on the computing environment.

It also depends on the algorithm. There are ways to speed-up the basic method.

Sieve improvement

One needn't compute all those square-roots of ${\displaystyle a^{2}-N}$ . Look again at this tableau for ${\displaystyle N=2345678917}$ .

A:	48433	48434	48435	48436
Bsq:	76572	173439	270308	367179
B:	276.7	416.5	519.9	605.9

One can tell at a glance that the first and third values of Bsq aren't squares. Squares end with 0, 1, 4, 5, 6, or 9. Not only that: the 11th and 13th values aren't squares, either. If a is increased by 10, Bsq will end with the same digit. One finds that a must end in 1 4 6 or 9, to make a square.

This can be generalized to any modulus. For that same N,

modulo 16:	Bsq must be	0 1 4 or 9
	so A must be	3 5 11 or 13
modulo 9:	Bsq must be	0 1 4 or 7
	so A must be	4 or 5
etc.

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:

Bsq ← A*A - N

if Bsq is a square, modulo Modulus:

FermatSieve(N, A, Aend, Astep * Modulus, NextModulus)

endif

A ← A + Astep

enddo

But one stops the recursion, 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 Bsq's with additions.

Multiplier improvement

Fermat's method works best when there's a factor near the square-root of N. Perhaps one can arrange for that to happen.

If one knew the approximate ratio of two factors (${\displaystyle d/c}$ ), then one could pick a rational number ${\displaystyle v/u}$  near that value. ${\displaystyle Nuv=cv*du}$ , and the factors are roughly equal: Fermat's, applied to Nuv, will find them quickly. Then ${\displaystyle gcd(N,cv)=c}$  and ${\displaystyle gcd(N,du)=d}$ . (Unless c divides u or d divides v.)

Generally, one doesn't know the ratio, but one can try various ${\displaystyle u/v}$  values, 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. See R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637-646, 1974.

Other improvements

See also J. McKee, "Speeding Fermat's factoring method", Mathematics of Computation, 68:1729-1737, 1999.