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.
[1] 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:[2] 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) Modern algorithms and computers can quickly factor univariate polynomials of degree more than 1000 having coefficients with thousands of digits.
Polynomial rings over the integers or over a field are unique factorization domains.
Moreover, this decomposition is unique up to multiplication of the factors by invertible constants.
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.
However, this is not a sufficient condition: Fröhlich and Shepherdson give examples of such fields for which no factorization algorithm can exist.
Kronecker's classical method is interesting only from a historical point of view; modern algorithms proceed by a succession of: and reductions: 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.
This defines a factorization of p into the product of an integer and a primitive polynomial.
It is a usual convention to choose the sign of the content such that the leading coefficient of the primitive part is positive.
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.
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.
This section describes textbook methods that can be convenient when computing by hand.
There are only a finite number of possible integer values for a factor of a.
is a univariate polynomial over the integers, assumed to be content-free and square-free, one starts by computing a bound
A simplified version of the LLL factorization algorithm is as follows: calculate a complex (or p-adic) root α of the polynomial
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
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
"Numerical factorization" refers commonly to the factorization of polynomials with real or complex coefficients, whose coefficients are only approximately known, generally because they are represented as floating point numbers.
's are known, an approximate factorization consists of finding a polynomial close to
For example, the number of irreducible factors of a polynomial is the nullity of its Ruppert matrix.
can be identified by square-free factorization via numerical GCD computation and rank-revealing on Ruppert matrices.
Several algorithms have been developed and implemented for numerical factorization as an on-going subject of research.