Fermat's factorization method

Fermat's factorization method

Fermat's factorization method is based on the representation of an odd integer as the difference of two squares: :N = a^2 - b^2. That difference is algebraically factorable as (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 N=cd is a factorization of "N", then :N = [(c+d)/2] ^2 - [(c-d)/2] ^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.

The basic method

One tries various values of "a", hoping that a^2-N = b^2 is a square.

:FermatFactor(N): // N should be odd::A ← ceil(sqrt(N))::Bsq ← A*A - N::while Bsq isn't a square::::A ← A + 1:::Bsq ← A*A - N // equivalently: Bsq ← Bsq + 2*A + 1::endwhile::return A - sqrt(Bsq) // or A + sqrt(Bsq)

For example, to factor N=5959, one computes

The third try produces a square. A=80, B=21, and the factors 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 - sqrt N = (sqrt d - sqrt c)^2 / 2 = (sqrt 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 {left(4N ight)}^{1/4} from sqrt N 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 sqrt{N}, 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.348017.547915.147830.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 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 c > sqrt{N}; use Fermat for factors between sqrt{N} and c. This gives a bound for trial division which is c - sqrt{c^2 - N}. In the above example, with c = 48436 the bound for trial division is 47830. A reasonable choice could be c = 55000 giving a bound of 28937.

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

A: 60001 60002
B: 35418.1 35419.8
A-B: 24582.9 24582.2

ieve improvement

One needn't compute all the square-roots of a^2-N, nor even examine all the values for a. Examine the tableau for N=2345678917:

A: 4843348434 48435 48436
B: 276.7416.5 519.9 605.9

One can quickly tell that none of these values of Bsq are squares. Squares end with 0, 1, 4, 5, 9, or 16 modulo 20. The values repeat with each increase of a by 10. For this example 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, a^2 must be 1 mod 20, which means that a is 1 or 9 mod 10; it will produce a Bsq which ends in 4 mod 20, and if Bsq is a 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 is5
so a^2 can only be9
and a must be3 or 5 modulo 16
modulo 9: Squares are 0, 1, 4, or 7
N mod 9 is7
so a^2 can only be7
and a must be4 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::::Bsq ← A*A - N:::if Bsq 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 "a"'s step-size is constant, one can compute successive Bsq'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 (d/c), then one can pick a rational number v/u near that value. Nuv = cv * du, and the factors are roughly equal: Fermat's, applied to "Nuv", will find them quickly. Then gcd(N,cv)=c and gcd(N,du)=d. (Unless "c" divides "u" or "d" divides "v".)

Generally, one does not know the ratio, but one can try various u/v 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 O(N^{1/3}) 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 sieve 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 "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".

See also J. McKee, " [http://www.ams.org/mcom/1999-68-228/S0025-5718-99-01133-3/home.html Speeding Fermat's factoring method] ", "Mathematics of Computation", 68:1729-1737 (1999).

External links

* [http://www.patrickkonsor.com/code/ Java Implementation Of Fermat's method and trial division]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Euler's factorization method — is a method of factorization based upon representing a positive integer N as the sum of two squares in two different ways :N = a^2+ b^2 = c^2+ d^2 (1)Although the algebraic factorization of binomial numbers cannot factor sums of two squares… …   Wikipedia

  • Dixon's factorization method — In number theory, Dixon s factorization method (also Dixon s random squares method[1] or Dixon s algorithm) is a general purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which …   Wikipedia

  • Fermat number — In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form:F {n} = 2^{2^{ overset{n} {} + 1where n is a nonnegative integer. The first nine Fermat numbers are OEIS|id=A000215:As of|2008 …   Wikipedia

  • Pierre de Fermat — Born August 17, 1601( …   Wikipedia

  • Shanks' square forms factorization — is a method for integer factorization, which was devised by Daniel Shanks as an improvement on Fermat s factorization method.The success of Fermat s method depends on finding integers x , and y such that x 2 − y 2 = N , where N is the integer to… …   Wikipedia

  • Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia

  • Faktorisierungsmethode von Fermat — Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Er berechnet zu einer ungeraden, zusammengesetzten Zahl n zwei Teiler a und b, für die gilt. Die Faktorisierungsmethode von Fermat hat nur… …   Deutsch Wikipedia

  • Methode de factorisation de Fermat — Méthode de factorisation de Fermat En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers. Sommaire 1 Intuition 2 Méthode de base 2.1 Analyse …   Wikipédia en Français

  • Méthode De Factorisation De Fermat — En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers. Sommaire 1 Intuition 2 Méthode de base 2.1 Analyse …   Wikipédia en Français

  • Méthode de factorisation de fermat — En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers. Sommaire 1 Intuition 2 Méthode de base 2.1 Analyse …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”