Factorization of Polynomials - Formulation of The Question

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 may be, theoretically, factorized into the product of an invertible 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.

This factorization is theoretical. Here computer algorithms are needed that, for a given polynomial ring and any polynomial in it, effectively produce the answer in a finite number of sets.

This depends strongly on the choice of 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 factorized into linear factors over the complex field C, while there are polynomials of any degree that are irreducible over the field of rationals Q. Similarly, over the field of reals, the irreducible factors have a degree not greater than two.

On the other hand, over R and C, the coefficients of the input polynomials and of the factors may not be given exactly. Only approximations may be given. Therefore an algorithm that gives a correct answer for every input cannot exist. It follows that for real or complex coefficients, one does not talk of polynomial factorization but of root-finding algorithms.

Thus 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. Fröhlich and Shepherson have provided 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: indeed, to factorize over the rationals, the first step consists in reducing the problem to a factorization over the integers.

Except for Kronecker's method, which is interesting only from a historical point of view, all the algorithms proceed by a succession partial factorizations that are byproducts of greatest common divisor computations.

• Primitive part–content factorization
• Square-free factorization
• Distinct-degree factorization over finite fields

Also reductions:

• From the multivariate case to the univariate one
• From coefficients in a purely transcendental extension to the multivariate case over the ground field (see below)
• From coefficients in an algebraic extension to coefficients in the ground field
• From rational coefficients to integer coefficients (see below)
• From integer coefficients to coefficients in a prime field with p elements, for a well chosen p.