Factorization of polynomials

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.
The first polynomial factorization algorithm was published by Theodor von Schubert in 1793. Leopold Kronecker rediscovered Schubert's algorithm in 1882 and extended it to multivariate polynomials and coefficients in an algebraic extension. But most of the knowledge on this topic is not older than circa 1965 and the first computer algebra systems:
When the long-known finite step algorithms were first put on computers, they turned out to be highly inefficient. The fact that almost any uni- or multivariate polynomial of degree up to 100 and with coefficients of a moderate size (up to 100 bits) can be factored by modern algorithms in a few minutes of computer time indicates how successfully this problem has been attacked during the past fifteen years. (Erich Kaltofen, 1982)
Nowadays, modern algorithms and computers can quickly factor univariate polynomials of degree more than 1000 having coefficients with thousands of digits.
Formulation of the question.
Polynomial rings over the integers or over a field are unique factorization domains. This means that every element of these rings is a product of a constant and a product of irreducible polynomials (those that are not the product of two non-constant polynomials). Moreover, this decomposition is unique up to multiplication of the factors by invertible constants.
Factorization depends on the base field. For example, the fundamental theorem of algebra, which states that every polynomial with complex coefficients has complex roots, implies that a polynomial with integer coefficients can be factored (with root-finding algorithms) into linear factors over the complex field C. Similarly, over the field of reals, the irreducible factors have degree at most two, while there are polynomials of any degree that are irreducible over the field of rationals Q.
The question of polynomial factorization makes sense only for coefficients in a "computable field" whose every element may be represented in a computer and for which there are algorithms for the arithmetic operations. However, this is not a sufficient condition: Fröhlich and Shepherdson give examples of such fields for which no factorization algorithm can exist.
The fields of coefficients for which factorization algorithms are known include prime fields (i.e., the field of rationals and prime modular arithmetic) and their finitely generated field extensions. Integer coefficients are also tractable. Kronecker's classical method is interesting only from a historical point of view; modern algorithms proceed by a succession of:
and reductions:
Primitive part–content factorization.
In this section, we show that factoring over Q (the rational numbers) and over Z (the integers) is essentially the same problem.
The "content" of a polynomial "p" ∈ Z["X"], denoted "cont("p")", is, up to its sign, the greatest common divisor of its coefficients. The "primitive part" of "p" is primpart("p")="p"/cont("p"), which is a primitive polynomial with integer coefficients. This defines a factorization of "p" into the product of an integer and a primitive polynomial. This factorization is unique up to the sign of the content. It is a usual convention to choose the sign of the content such that the leading coefficient of the primitive part is positive.
For example,
is a factorization into content and primitive part.
Every polynomial "q" with rational coefficients may be written
where "p" ∈ Z["X"] and "c" ∈ Z: it suffices to take for "c" a multiple of all denominators of the coefficients of "q" (for example their product) and "p" = "cq". The "content" of "q" is defined as:
and the "primitive part" of "q" is that of "p". As for the polynomials with integer coefficients, this defines a factorization into a rational number and a primitive polynomial with integer coefficients. This factorization is also unique up to the choice of a sign.
For example,
is a factorization into content and primitive part.
Gauss proved that the product of two primitive polynomials is also primitive (Gauss's lemma). This implies that a primitive polynomial is irreducible over the rationals if and only if it is irreducible over the integers. This implies also that the factorization over the rationals of a polynomial with rational coefficients is the same as the factorization over the integers of its primitive part. Similarly, the factorization over the integers of a polynomial with integer coefficients is the product of the factorization of its primitive part by the factorization of its content.
In other words, an integer GCD computation reduces the factorization of a polynomial over the rationals to the factorization of a primitive polynomial with integer coefficients, and the factorization over the integers to the factorization of an integer and a primitive polynomial.
Everything that precedes remains true if Z is replaced by a polynomial ring over a field "F" and Q is replaced by a field of rational functions over "F" in the same variables, with the only difference that "up to a sign" must be replaced by "up to the multiplication by an invertible constant in "F"". This reduces the factorization over a purely transcendental field extension of "F" to the factorization of multivariate polynomials over "F".
Square-free factorization.
If two or more factors of a polynomial are identical, then the polynomial is a multiple of the square of this factor. The multiple factor is also a factor of the polynomial's derivative (with respect to any of the variables, if several). 
For univariate polynomials, multiple factors are equivalent to multiple roots (over a suitable extension field). For univariate polynomials over the rationals (or more generally over a field of characteristic zero), Yun's algorithm exploits this to efficiently factorize the polynomial into square-free factors, that is, factors that are not a multiple of a square, performing a sequence of GCD computations starting with gcd("f"("x"), "f" '("x")). To factorize the initial polynomial, it suffices to factorize each square-free factor. Square-free factorization is therefore the first step in most polynomial factorization algorithms.
Yun's algorithm extends this to the multivariate case by considering a multivariate polynomial as a univariate polynomial over a polynomial ring.
In the case of a polynomial over a finite field, Yun's algorithm applies only if the degree is smaller than the characteristic, because, otherwise, the derivative of a non-zero polynomial may be zero (over the field with "p" elements, the derivative of a polynomial in "x""p" is always zero). Nevertheless, a succession of GCD computations, starting from the polynomial and its derivative, allows one to compute the square-free decomposition; see Polynomial factorization over finite fields#Square-free factorization.
Classical methods.
This section describes textbook methods that can be convenient when computing by hand. These methods are not used for computer computations because they use integer factorization, which is currently slower than polynomial factorization.
Obtaining linear factors.
All linear factors with rational coefficients can be found using the rational root test. If the polynomial to be factored is formula_5, then all possible linear factors are of the form formula_6, where formula_7 is an integer factor of formula_8 and formula_9 is an integer factor of formula_10. All possible combinations of integer factors can be tested for validity, and each valid one can be factored out using polynomial long division. If the original polynomial is the product of factors at least two of which are of degree 2 or higher, this technique only provides a partial factorization; otherwise the factorization is complete. In particular, if there is exactly one non-linear factor, it will be the polynomial left after all linear factors have been factorized out. In the case of a cubic polynomial, if the cubic is factorizable at all, the rational root test gives a complete factorization, either into a linear factor and an irreducible quadratic factor, or into three linear factors.
Kronecker's method.
Since integer polynomials must factor into integer polynomial factors, and evaluating integer polynomials at integer values must produce integers, the integer values of a polynomial can be factored in only a finite number of ways, and produce only a finite number of possible polynomial factors.
For example, consider
If this polynomial factors over Z, then at least one of its factors formula_12 must be of degree two or less, so formula_12 is uniquely determined by three values. Thus, we compute three values formula_14, formula_15 and formula_16. If one of these values is 0, we have a linear factor. If the values are nonzero, we can list the possible factorizations for each. Now, 2 can only factor as
Therefore, if a second degree integer polynomial factor exists, it must take one of the values
and likewise for "p"(1). There are eight factorizations of 6 (four each for 1×6 and 2×3), making a total of 4×4×8 = 128 possible triples ("p"(0), "p"(1), "p"(−1)), of which half can be discarded as the negatives of the other half. Thus, we must check 64 explicit integer polynomials formula_17 as possible factors of formula_18. Testing them exhaustively reveals that
constructed from ("g"(0), "g"(1), "g"(−1)) = (1,3,1) factors formula_18.
Dividing "f"("x") by "p"("x") gives the other factor formula_21, so that formula_22.
Now one can test recursively to find factors of "p"("x") and "q"("x"), in this case using the rational root test. It turns out they are both irreducible, so the irreducible factorization of "f"("x") is:
Modern methods.
Factoring univariate polynomials over the integers.
If formula_18 is a univariate polynomial over the integers, assumed
to be content-free
and square-free, one starts by computing a bound formula_25
such that any factor formula_26 has coefficients of
absolute value bounded by formula_25. This way, if formula_28 is
an integer larger than formula_29, and if formula_26 is known modulo
formula_28, then formula_26 can be reconstructed from its image mod formula_28.
The Zassenhaus algorithm proceeds as follows. First, choose a prime
number formula_34 such that the image of formula_18 mod formula_34
remains square-free, and of the same degree as formula_18.
Then factor formula_18 mod formula_34. This produces integer polynomials formula_40 whose product matches formula_18 mod formula_34. Next, apply Hensel lifting; this updates the formula_43 in such a way that their product matches formula_18 mod formula_45, where formula_46 is large enough that formula_45 exceeds formula_29: thus each formula_43 corresponds to a well-defined integer polynomial. Modulo formula_45, the polynomial formula_18 has formula_52 factors (up to units): the products of all subsets of formula_53 mod formula_45. These factors modulo formula_45 need not correspond to "true" factors of formula_18 in formula_57, but we can easily test them by division in formula_57. This way, all irreducible true factors can be found by checking at most formula_52 cases, reduced to formula_60 cases by skipping complements. If formula_18 is reducible, the number of cases is reduced further by removing those formula_43 that appear in an already found true factor. The Zassenhaus algorithm processes each case (each subset) quickly, however, in the worst case, it considers an exponential number of cases.
The first polynomial time algorithm for factoring rational polynomials was discovered by Lenstra, Lenstra and Lovász and is an application of the Lenstra–Lenstra–Lovász lattice basis reduction (LLL) algorithm .
A simplified version of the LLL factorization algorithm is as follows: calculate a complex (or "p"-adic) root α of the polynomial formula_18 to high precision, then use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm to find an approximate linear relation between 1, α, α2, α3, . . . with integer coefficients, which might be an exact linear relation and a polynomial factor of formula_18. One can determine a bound for the precision that guarantees that this method produces either a factor, or an irreducibility proof. Although this method finishes in polynomial time, it is not used in practice because the lattice has high dimension and huge entries, which makes the computation slow.
The exponential complexity in the Zassenhaus algorithm comes from a combinatorial problem: how to select the right subsets of formula_40. State-of-the-art factoring implementations work in a manner similar to Zassenhaus, except that the combinatorial problem is translated to a lattice problem that is then solved by LLL. In this approach, LLL is not used to compute coefficients of factors, but rather to compute vectors with formula_66 entries in {0,1} that encode the subsets of formula_40 corresponding to the irreducible true factors.
Factoring over algebraic extensions (Trager's method).
We can factor a polynomial formula_68, where the field formula_69 is a finite extension of formula_70. First, using square-free factorization, we may suppose that the polynomial is square-free. Next we define the quotient ring formula_71 of degree formula_72; this is not a field unless formula_12 is irreducible, but it is a reduced ring since formula_12 is square-free. Indeed, ifformula_75is the desired factorization of "p"("x"), the ring decomposes uniquely into fields as:
We will find this decomposition without knowing the factorization. First, we write "L" explicitly as an algebra over formula_70: we pick a random element formula_78, which generates formula_79 over formula_70 with high probability by the primitive element theorem. If this is the case, we can compute the minimal polynomial formula_81 of formula_82 over formula_70, by finding a formula_70-linear relation among 1, "α", . . . , "αn". Using a factoring algorithm for rational polyomials, we factor into irreducibles in formula_85:
Thus we have:
where formula_82 corresponds to formula_89. This must be isomorphic to the previous decomposition of formula_79. 
The generators of "L" are "x" along with the generators of formula_69 over formula_70; writing these as a polynomials in formula_82, we can determine the embeddings of formula_94 and formula_69 into each component formula_96. By finding the minimal polynomial of formula_94 in formula_98, we compute formula_99, and thus factor formula_12 over formula_101