Factorization

Factorization was first considered by ancient Greek mathematicians in the case of integers.

Although integer factorization is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the RSA cryptosystem to implement public-key cryptography.

There are number systems, such as certain rings of algebraic integers, which are not unique factorization domains.

For computing the factorization of an integer n, one needs an algorithm for finding a divisor q of n or deciding that n is prime.

For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of r that is not smaller than q and not greater than √r.

This needs to have a table of prime numbers that may be generated for example with the sieve of Eratosthenes.

As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not.

In fact, applying the above method would require more than 10000 divisions, for a number that has 10 decimal digits.

However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers.

[2] Even though the structure of the factorization is known in these cases, the ais generally cannot be computed in terms of radicals (nth roots), by the Abel–Ruffini theorem.

The systematic use of algebraic manipulations for simplifying expressions (more specifically equations) may be dated to 9th century, with al-Khwarizmi's book The Compendious Book on Calculation by Completion and Balancing, which is titled with two such types of manipulation.

However, even for solving quadratic equations, the factoring method was not used before Harriot's work published in 1631, ten years after his death.

[3] In his book Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas, Harriot drew tables for addition, subtraction, multiplication and division of monomials, binomials, and trinomials.

Then, in a second section, he set up the equation aa − ba + ca = + bc, and showed that this matches the form of multiplication he had previously provided, giving the factorization (a − b)(a + c).

The above methods may be used for letting the sum side of some identity appear in an expression, which may therefore be replaced by a product.

one has the following real factorizations (one passes from one to the other by changing k into n – k or n + 1 – k, and applying the usual trigonometric formulas:

The cosines that appear in these factorizations are algebraic numbers, and may be expressed in terms of radicals (this is possible because their Galois group is cyclic); however, these radical expressions are too complicated to be used, except for low values of n. For example,

To express rational factorizations of sums and differences or powers, we need a notation for the homogenization of a polynomial: if

For polynomials, factorization is strongly related with the problem of solving algebraic equations.

The fundamental theorem of arithmetic may be generalized to this case, stating that polynomials with integer or rational coefficients have the unique factorization property.

Besides the heuristics above, only a few methods are suitable for hand computations, which generally work only for polynomials of low degree, with few nonzero coefficients.

Then one divides out the greater common divisor p of the coefficients of this polynomial for getting the primitive part, the content being

Primitive part-content factorization (see above) reduces the problem of searching for rational roots to the case of polynomials with integer coefficients having no non-trivial common divisor.

If it has a rational root, its denominator must divide a evenly and it may be written as a possibly reducible fraction

[9] There are also formulas for roots of cubic and quartic polynomials, which are, in general, too complicated for practical use.

The Abel–Ruffini theorem shows that there are no general root formulas in terms of radicals for polynomials of degree five or higher.

Galois theory is based on a systematic study of the relations between roots and coefficients, that include Vieta's formulas.

There is an explicit example of a field F such that there cannot exist any factorization algorithm in the Euclidean domain F[x] of the univariate polynomials over F. In algebraic number theory, the study of Diophantine equations led mathematicians, during 19th century, to introduce generalizations of the integers called algebraic integers.

This lack of unique factorization is a major difficulty for solving Diophantine equations.

As this is not always possible, one generally considers the "LUP decomposition" having a permutation matrix as its third factor.