Fermat's factorization method

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 algebraically 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.

Basic method[edit]

One tries various values of a, hoping that , a square.

FermatFactor(N): // N should be odd
    a ← ceil(sqrt(N))
    b2 ← a*a - N
    while b2 is not a square:
        a ← a + 1    // equivalently: b2 ← b2 + 2*a + 1
        b2 ← a*a - N //               a ← a + 1
    return a - sqrt(b2) // or a + sqrt(b2)

For example, to factor , the first try for a is the square root of 5959 rounded up to the next integer, which is 78. Then, . 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. So, , , and the factors of 5959 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; this is independent of the size of N.[citation needed]

Graphic example[edit]

All integer divisors can be represented as points in a divisor plane. The -axis represents the divisor values, the -axis corresponds to an integer number line (for better comprehensibility the - and -axis is scaled in a ratio of 1 to 16).

The divisor points in a divisor plane have following properties (and some more):

  • All divisors of the divisor plane can be assigned to a parabola of the form .
  • All complementary divisor pairs of a number lie on a common parabola.
  • The addition of two complementary divisors of a number yields the coefficient of the common parabola.


Fermat's factorization in the divisor plane

The complementary divisor pairs of are the trivial divisors and the non-trivial divisors .

The intersections of parabolas of the form with parallels to -axis thus provide factor candidates. Moving the parabola yields either the non-trivial or, in the very last step, the trivial divisors of a number.

The first parabola with a vertex value greater than becomes (because of ). After repeated shifting, the parabola and the divisors and were found. The x-coordinate of the vertex value lies at .

The number is therefore the difference of the squares . The non-trivial divisors can be calculated as and .

Parabolas of the form are not included in Fermat's method (the resulting numbers are all even).

Fermat's and trial division[edit]

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

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
ab 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 , 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 ; use Fermat's method 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 60,001 60,002
b2 1,254,441,084 1,254,561,087
b 35,418.1 35,419.8
ab 24,582.9 24,582.2

Sieve improvement[edit]

It is not necessary to compute all the square-roots of , nor even examine all the values for a. Consider the table for :

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

One can quickly tell that none of these values of 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), 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 a is 1, 9, 11 or 19 mod 20; it will produce a 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 ,

modulo 16: Squares are 0, 1, 4, or 9
N mod 16 is 5
so 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 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)
     a ← a + astep

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.

Multiplier improvement[edit]

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

If the approximate ratio of two factors () is known, then the rational number can be picked 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, if the ratio is not known, various 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 time.[1]

Other improvements[edit]

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 , 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.

See also[edit]


  1. ^ Lehman, R. Sherman (1974). "Factoring Large Integers" (PDF). Mathematics of Computation. 28 (126): 637–646. doi:10.2307/2005940. 

External links[edit]