↑ arvau

Wikipedia / 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:

That difference is algebraically; if neither factor equals one, it is a proper factorization of N.

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 by itself.

Basic method

One tries various values of a, 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)

, the first try for a is the square root of rounded up to the next integer, which is . 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., and the factors of .

Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of a and b is the smallest factor ≥ the square-root of N is the largest factor ≤ root-N, that shows that N is prime.

, let c.

If 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, the method requires only one step; this is independent of the size of N.

Fermat's and trial division

Consider trying to factor the prime number , but also compute b and rounded up to the next integer, which is 48,433, we can tabulate:In practice, one wouldn't bother with that last row until b is an integer. But observe that if N, 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.

giving a bound of 28937.

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

Sieve improvement

are squares:, nor even examine all the values for . 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 must be 1 mod 20, which means that which ends in 4 mod 20 and, if square, will end in 2 or 8 mod 10.

,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 ()/ 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.

) is known, then a rational number, and Fermat's method, applied to Nuv. (Unless c divides u or d divides v.)

values can be tried, and try to factor each resulting Nuv time.

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

Notes

References