Factorization of Polynomials

In mathematics and computer algebra, factorization of polynomials or polynomial factorization refers to factoring a polynomial with coefficients in a given field or in the integers into irreducible factors with coefficients in same domain. Polynomial factorization is one of the fundamental tools of the computer algebra systems.

The specification of the field is fundamental, as, for example, the polynomial x2−2 is irreducible over the integers and the rationals numbers (it has no non-constant factors), while it is factorized into over the field of real numbers.

Theoretically, there is always a factorization into irreducible polynomials of any polynomials with coefficients in a field: that is, polynomial rings are unique factorization domains. However, one wants an algorithm to perform this factorization in a finite number of steps. Therefore factorization over the real or the complex numbers is not considered here, since in most cases only approximate answers can be given, through root-finding algorithms. Also, there are explicitly given fields for which no polynomial factorization algorithm can exist. In practice, polynomial factorization is considered only for coefficients in the integers or in a finitely generated extension of a prime field (including finite fields, rational numbers, and algebraic numbers).

The history of polynomial factorization starts with Hermann Schubert who in 1793 described the first polynomial factorization algorithm, and Leopold Kronecker, who 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. In a survey of the subject, Erich Kaltofen wrote in 1982 (see the bibliography, below):

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.