Fermat's factorization method
Encyclopedia
Fermat's factorization
method, named after Pierre de Fermat
, is based on the representation of an odd
integer
as the difference of two squares
:
That difference is algebra
ically factorable as
; if neither factor equals one, it is a proper factorization of N.
Each odd number has such a representation. Indeed, if
is a factorization of N, then
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.
is a square.
For example, to factor
, one computes
The third try produces a square.
, 
, and the factors are 
, and 
.
Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is,
is the smallest factor ≥ the square-root of N. And so 
is the largest factor ≤ root-N. If the procedure finds 
, that shows that N is prime.
For
, let c be the largest subroot factor. 
, so the number of steps is approximately 
.
If N is prime (so that
), one needs 
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 
from 
the method requires only one step. Note, that this is independent of the size of N.
, 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
, 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.
This all suggests a combined factoring method. Choose some bound
; use Fermat for factors between 
and 
. This gives a bound for trial division which is 
. In the above example, with 
the bound for trial division is 47830. A reasonable choice could be 
giving a bound of 28937.
In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
, nor even examine all the values for 
. Examine the tableau for 
:
One can quickly tell that none of these values of b2 are squares. Squares end with 0, 1, 4, 5, 9, or 16 modulo
20. The values repeat with each increase of
by 10. For this example, adding '-17' mod 20 (or 3), 
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, 
must be 1 mod 20, which means that 
is 1 or 9 mod 10; it will produce a b2 which ends in 4 mod 20 and, if square, 
will end in 2 or 8 mod 10.
This can be performed with any modulus. Using the same
,
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:
But one stops the recursion, when few a-values remain; that is, when (aend-astart)/astep is small. Also, because as step-size is constant, one can compute successive b2's with additions.
If one knows the approximate ratio of two factors (
), then one can pick a rational number 
near that value. 
, and the factors are roughly equal: Fermat's, applied to Nuv, will find them quickly. Then 
and 
. (Unless c divides u or d divides v.)
Generally, one does not know the ratio, but one can try various
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 
time.
See R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637-646, 1974.
and general number field sieve
, the best-known algorithms for factoring "worst-case" large semiprimes. The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of
, 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.
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
method, named after Pierre de Fermat
Pierre de Fermat
Pierre de Fermat was a French lawyer at the Parlement of Toulouse, France, and an amateur mathematician who is given credit for early developments that led to infinitesimal calculus, including his adequality...
, is based on the representation of an odd
Even and odd numbers
In mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...
integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
as the difference of two squares
Difference of two squares
In mathematics, the difference of two squares, or the difference of perfect squares, is when a number is squared, or multiplied by itself, and is then subtracted from another squared number...
:
That difference is algebra
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
ically factorable as
; if neither factor equals one, it is a proper factorization of N.Each odd number has such a representation. Indeed, if
is a factorization of N, thenSince 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.
The basic method
One tries various values of a, hoping that is a square.
FermatFactor(N): // N should be odd
a ← ceil(sqrt(N))
b2 ← a*a - N
while b2 isn't a square:
a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1
b2 ← a*a - N // a ← a + 1
endwhile
return a - sqrt(b2) // or a + sqrt(b2)
For example, to factor
, one computes
| a: | 78 | 79 | 80 |
|---|---|---|---|
| b2: | 125 | 282 | 441 |
The third try produces a square.
, , and the factors are , and .Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b. That is,
is the smallest factor ≥ the square-root of N. And so is the largest factor ≤ root-N. If the procedure finds , that shows that N is prime.For
, let c be the largest subroot factor. , so the number of steps is approximately .If N is prime (so that
), one needs 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 from the method requires only one step. Note, that this is independent of the size of N.Fermat's and trial division
Let's try to factor the prime number N=2345678917, but also compute b and a-b throughout. Going up from, we can tabulate:| a: | 48433 | 48434 | 48435 | 48436 |
| b2: | 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
, 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.
This all suggests a combined factoring method. Choose some bound
; use Fermat for factors between and . This gives a bound for trial division which is . In the above example, with the bound for trial division is 47830. A reasonable choice could be giving a bound of 28937.In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
| a: | 60001 | 60002 |
| b2: | 1254441084 | 1254561087 |
| b: | 35418.1 | 35419.8 |
| a-b: | 24582.9 | 24582.2 |
Sieve improvement
One needn't compute all the square-roots of, nor even examine all the values for . Examine the tableau for :| a: | 48433 | 48434 | 48435 | 48436 |
| b2: | 76572 | 173439 | 270308 | 367179 |
| b: | 276.7 | 416.5 | 519.9 | 605.9 |
One can quickly tell that none of these values of b2 are squares. Squares end with 0, 1, 4, 5, 9, or 16 modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
20. The values repeat with each increase of
by 10. For this example, adding '-17' mod 20 (or 3), 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, must be 1 mod 20, which means that is 1 or 9 mod 10; it will produce a b2 which ends in 4 mod 20 and, if square, will end in 2 or 8 mod 10.This can be performed with any modulus. Using the same
,| modulo 16: | Squares are | 0, 1, 4, or 9 |
| N mod 16 is | 5 | |
so  can only be | 9 | |
and  must be | 3 or 5 modulo 16 | |
| modulo 9: | Squares are | 0, 1, 4, or 7 |
| N mod 9 is | 7 | |
so  can only be | 7 | |
and  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 one stops the recursion, when few a-values remain; that is, when (aend-astart)/astep is small. Also, because as step-size is constant, one can compute successive b2's with additions.
Multiplier improvement
Fermat's method works best when there is a factor near the square-root of N. Perhaps one can arrange for that to happen.If one knows the approximate ratio of two factors (
), then one can pick a rational number near that value. , and the factors are roughly equal: Fermat's, applied to Nuv, will find them quickly. Then and . (Unless c divides u or d divides v.)Generally, one does not know the ratio, but one can try various
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 time.See R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637-646, 1974.
Other improvements
The fundamental ideas of Fermat's factorization method are the basis of the quadratic sieveQuadratic sieve
The quadratic sieve algorithm is a modern integer factorization algorithm and, in practice, the second fastest method known . It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve...
and general number field sieve
General number field sieve
In number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...
, the best-known algorithms for factoring "worst-case" large semiprimes. The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of
, 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.