Fermat's factorization method
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: : N = a^2 - b^2.
≈ 9 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:
- N=a2−b2.
That difference is algebraically factorable as (a+b)(a−b); if neither factor equals one, it is a proper factorization of N.
Every odd number can be represented as such. If N=cd is a factorization of N, then: N=(c+d2)2−(c−d2)2.
Since N is odd, both c and d are also odd, and hence the two terms in parentheses are integers.
In its simplest form, Fermat's method can be even slower than trial division (in the worst case). Nonetheless, combining Fermat's method and trial division can be more efficient than either method alone.
Basic method
edit edit sourceOne tries various values of a, hoping that a2−N=b2, 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 N=5959, the first try for a is the square root of 5959 rounded up to the next integer, which is 78. Then b2=782−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: | 1 | 2 | 3 |
|---|---|---|---|
| a | 78 | 79 | 80 |
| b2 | 125 | 282 | 441 |
| b | 11.18 | 16.79 | 21 |
The third try produces the perfect square of 441. Thus, a=80, b=21, and the factors of 5959 are a−b=59 and 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, a+b is the smallest factor ≥ the square-root of N, and so a−b=N/(a+b) is the largest factor ≤ root-N. If the procedure finds N=1⋅N, that shows that N is prime.
For N=cd, let c be the largest subroot factor. a=(c+d)/2, so the number of steps is approximately (c+d)/2−N=(d−c)2/2=(N−c)2/2c.
If N is prime (so that c=1), one needs 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 (4N)1/4 from N, the method requires only one step; this is independent of the size of N.[citation needed]
Fermat's and trial division
edit edit sourceConsider trying to factor the prime number N = 2,345,678,917, but also compute b and a − b throughout. Going up from N rounded up to the next integer, which is 48,433, we can tabulate:
| Try | 1st | 2nd | 3rd | 4th |
|---|---|---|---|---|
| a | 48,433 | 48,434 | 48,435 | 48,436 |
| b2 | 76,572 | 173,439 | 270,308 | 367,179 |
| b | 276.7 | 416.5 | 519.9 | 605.9 |
| a − b | 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 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 amax>N; use Fermat's method for factors between N and amax. This gives a bound for trial division which is amax−amax2−N. In the above example, with amax=48436 the bound for trial division is 47830. A reasonable choice could be amax=55000 giving a bound of 28937.
In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
| a | 60,001 | 60,002 |
|---|---|---|
| b2 | 1,254,441,084 | 1,254,561,087 |
| b | 35,418.1 | 35,419.8 |
| a − b | 24,582.9 | 24,582.2 |
Sieve improvement
edit edit sourceWhen considering the table for N=2345678917, one can quickly tell that none of the values of b2 are squares:
| a | 48,433 | 48,434 | 48,435 | 48,436 |
|---|---|---|---|---|
| b2 | 76,572 | 173,439 | 270,308 | 367,179 |
| b | 276.7 | 416.5 | 519.9 | 605.9 |
It is not necessary to compute all the square-roots of a2−N, nor even examine all the values for a. Squares are always congruent to 0, 1, 4, 5, 9, 16 modulo 20, because these are the quadratic residues of 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), a2−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, a2 must be 1 mod 20, which means that a is 1, 9, 11 or 19 mod 20; it will produce a b2 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 N=2345678917,
| modulo 16: | Squares are | 0, 1, 4, or 9 |
| N mod 16 is | 5 | |
| so a2 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 a2 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 enddoBut 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.
Multiplier improvement
edit edit sourceFermat's method works best when there is a factor near the square-root of N.
If the approximate ratio of two factors (d/c) is known, then a rational number v/u can be picked near that value. Nuv=cv⋅du, and Fermat's method, applied to Nuv, will find the factors cv and du quickly. Then gcd(N,cv)=c and gcd(N,du)=d. (Unless c divides u or d divides v.)
Generally, if the ratio is not known, various 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 O(N1/3) time.[1]
Other improvements
edit edit sourceThe 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 a2−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.
See also
edit edit source- 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
Notes
edit edit source- ^ Lehman, R. Sherman (1974). "Factoring Large Integers" (PDF). Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940. JSTOR 2005940. Wikipedia revision 1373044543, retrieved 2026-11-18
References
edit edit source- 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.
External links
edit edit source- Fermat's factorization running time, at blogspot.in
- Fermat's Factorization Online Calculator, at windowspros.ru
- Italics indicate that algorithm is for numbers of special forms
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373044543 under CC BY-SA 4.0; modifications have been made.