# Fermat's factorization method

(Redirected from Fermat factorization)

Fermat's factorization method, named after Pierre de Fermat, is based on the 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.

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

${\displaystyle N=\left({\frac {c+d}{2}}\right)^{2}-\left({\frac {c-d}{2}}\right)^{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). Nonetheless, the combination of trial division and Fermat's is more effective than either.

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

 Try: a b2 1 2 3 78 79 80 125 282 441 11.18 16.79 21

The third try produces the perfect square of 441. So, ${\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 d=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]

## Fermat's and trial division

Consider trying to factor the prime number N = 2345678917, but also compute b and ab throughout. Going up from ${\displaystyle {\sqrt {N}}}$, we can tabulate:

a b2 b a − b 48,433 48,434 48,435 48,436 76,572 173,439 270,308 367,179 276.7 416.5 519.9 605.9 48,156.3 48,017.5 47,915.1 47,830.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 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 c>{\sqrt {N}}}$; use Fermat's method for factors between ${\displaystyle {\sqrt {N}}}$ and ${\displaystyle c}$. This gives a bound for trial division which is ${\displaystyle c-{\sqrt {c^{2}-N}}}$. In the above example, with ${\displaystyle c=48436}$ the bound for trial division is 47830. A reasonable choice could be ${\displaystyle c=55000}$ giving a bound of 28937.

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

a b2 60,001 60,002 1,254,441,084 1,254,561,087 35,418.1 35,419.8 24,582.9 24,582.2

## Sieve improvement

It is not necessary to compute all the square-roots of ${\displaystyle a^{2}-N}$, nor even examine all the values for a. Consider the table for ${\displaystyle N=2345678917}$:

 a b2 b 48,433 48,434 48,435 48,436 76,572 173,439 270,308 367,179 276.7 416.5 519.9 605.9

One can quickly tell that none of these values of ${\displaystyle b^{2}}$ are squares. 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}$,

 modulo 16: Squares are 0, 1, 4, or 9 N mod 16 is 5 so ${\displaystyle a^{2}}$ can only be 9 and a must be 3 or 5 or 11 or 13 modulo 16 modulo 9: Squares are 0, 1, 4, or 7 N mod 9 is 7 so ${\displaystyle a^{2}}$ can only be 7 and a must be 4 or 5 modulo 9

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.

A further modular improvement can be made by applying the division algorithm as an affine transformation, that is ${\displaystyle X=\beta x+a}$, ${\displaystyle Y=\beta y+b}$, ${\displaystyle N=\beta z+r}$, over any integer ring ${\displaystyle \mathbb {Z} _{\beta }}$ where ${\displaystyle \beta . After a small amount of algebra, one can conclude that ${\displaystyle \lfloor N/\beta ^{2}\rfloor -s=xy}$ and ${\displaystyle \lfloor ab/\beta \rfloor =t}$ where s and t are identical to determining the carries one does in multiplying the divisors over base ${\displaystyle \beta }$.[citation needed]

## Multiplier improvement

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 the rational number ${\displaystyle v/u}$ can be picked near that value. For example, if ${\displaystyle Y/X\approx q}$, then ${\displaystyle X\approx {\sqrt {N/q}}}$ is a good estimate for the smaller of a divisor pair. ${\displaystyle Nuv=cv\cdot 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.) A further generalization of this approach assumes that ${\displaystyle Y^{n}/X^{m}\approx q}$, meaning that ${\displaystyle X\approx N^{m/(m+n)}/q^{1/(m+n)}}$.

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]

## Other improvements

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 square mod n that, if nontrivial, can be used to factor n.