Factorization

Factorization is the process of finding prime factors. This article will only cover integer factorization.

If a and b are integers such that a × b = c, then both a and b are factors of c. As with all other integers, factors can be either prime or composite, so after checking that the number a is not prime using a primality test, we have to attempt the factorization of this number. The same can be said of the other factor b. So it can be seen that we have to proceed recursively in order to find all the prime factors of c.

Since almost all factorization methods use modular arithmetic, reading the modular arithmetic article is a prerequisite to understanding those methods.

There are two categories of factorization methods:

The "special purpose" methods whose execution time depends on the size (i.e., number of digits), or on other particular properties of the factors.

• Trial factoring: The fastest method for finding very small factors compared with the number to be factored (if the composite number is very large, this can be the only practical method).
• Rho Method: Asymptotically faster than trial factoring, but the overhead for small numbers makes this method convenient only for finding factors in the range of 10 to 20 digits.
• p-1: It finds a factor p if the largest prime factor of p-1 is small.
• p+1: Similar to p-1, but succeeds if p+1 has no large factors.
• ECM: This is the asymptotically fastest known method to find prime factors up to approximately 70 digits.

The "general purpose" methods whose run time depends only on the size of the number to be factored. These methods cannot be used in GIMPS because they would take too much time.

• Continued fraction factorization algorithm or CFRAC: It is a fast method to factorize numbers in the range 10 to 20 digits.
• Multiple polynomial quadratic sieve or MPQS: This is a very fast method for numbers in the range 30 to 100 digits.
• Self-initializing quadratic sieve or SIQS: A variant of MPQS, in general it is faster.
• General number field sieve or GNFS: This is the fastest known method when the number to be factored has more than 110 digits.
• Special number field sieve or SNFS: This is faster than GNFS but only works for numbers of a particular form.

Since most composite numbers have small factors (half of the numbers are multiples of 2, a third are multiples of 3 and so on) it pays to run factorization methods in the first category and then, if no factor is found in a reasonable amount of time (this depends on the length of the number to be factored), switch to another method in the second category, but if the threshold is too high and no factor is found with a method in the first category, the number remains unfactored, until a faster computer is used or another algorithm is invented.

Many factorization algorithms do not work if the number is a perfect power, so before attempting these methods a check must be performed in order to ensure that the number is not a perfect power. When the number to factor has a special form, if we know beforehand that it is not a perfect power we can proceed directly to factor it.

See also

• Factoring program
• Factoring Database

External links

• Integer factorization
• Factoring papers - FactorWorld
• Prime factorization algorithms - Wolfram Research/Mathematica
• Mersenneforum section on factoring programs links
• Dario Alpern's Online ECM and SIQS Factorization Calculator
• YAFU, developed by Ben Buhrow.