Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Factorization

From Prime-Wiki
Jump to: navigation, search

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.

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

External links