Factorization of polynomials
Top 10 Factorization of polynomials related articles
- 1 Formulation of the question
- 2 Primitive part–content factorization
- 3 Square-free factorization
- 4 Classical methods
- 5 Modern methods
- 6 See also
- 7 Bibliography
- 8 Further reading
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)
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 Shepherson 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:
- Square-free factorization
- Factorization over finite fields
- From the multivariate case to the univariate case.
- 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 (see below).
- 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 (see below).
Factorization of polynomials Formulation of the question articles: 14
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.
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.
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.
Factorization of polynomials Primitive part–content factorization articles: 7
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 xp 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.
Factorization of polynomials Square-free factorization articles: 2
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
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
- 1×2, 2×1, (−1)×(−2), or (−2)×(−1).
Therefore, if a second degree integer polynomial factor exists, it must take one of the values
- p(0) = 1, 2, −1, or −2
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
constructed from (g(0), g(1), g(−1)) = (1,3,1) factors
Dividing f(x) by p(x) gives the other factor
Factorization of polynomials Classical methods articles: 5
Factoring over finite fields
Factoring univariate polynomials over the integers
The Zassenhaus algorithm proceeds as follows. First, choose a prime
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 (Lenstra, Lenstra & Lovász 1982).
A simplified version of the LLL factorization algorithm is as follows: calculate a complex (or p-adic) root α of the polynomial
The exponential complexity in the Zassenhaus algorithm comes from a combinatorial problem: how to select the right subsets of
Factoring over algebraic extensions (Trager's method)
We can factor a polynomial
is the desired fractorization 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
Thus we have:
The generators of L are x along with the generators of
Factorization of polynomials Modern methods articles: 8
- Factorization § Polynomials, for elementary heuristic methods and explicit formulas
- FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, p. 172-182(1793)
- An example of degree 2401, taking 7.35 seconds, is found in Section 4 in: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, p. 163-170 (2011).
- Van der Waerden, Sections 5.4 and 5.6
- M. van Hoeij: Factoring polynomials and the knapsack problem. Journal of Number Theory, 95, 167-189, (2002).
- Fröhlich, A.; Shepherson, J. C. (1955), "On the factorisation of polynomials in a finite number of steps", Mathematische Zeitschrift, 62 (1): 331–334, doi:10.1007/BF01180640, ISSN 0025-5874
- Trager, B.M. (1976), "Algebraic Factoring and Rational Function Integration", Proc. SYMSAC 76, Symsac '76: 219–226, doi:10.1145/800205.806338
- Bernard Beauzamy, Per Enflo, Paul Wang (October 1994). "Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation". Mathematics Magazine. 67 (4): 243–257. doi:10.2307/2690843. JSTOR 2690843.CS1 maint: multiple names: authors list (link) (accessible to readers with undergraduate mathematics)
- Cohen, Henri (1993). A course in computational algebraic number theory. Graduate Texts in Mathematics. 138. Berlin, New York: Springer-Verlag. ISBN 978-3-540-55640-4. MR 1228206.
- Kaltofen, Erich (1982), "Factorization of polynomials", in B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra, Springer Verlag, pp. 95–113, CiteSeerX 10.1.1.39.7916
- Knuth, Donald E (1997). "4.6.2 Factorization of Polynomials". Seminumerical Algorithms. The Art of Computer Programming. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 978-0-201-89684-8.
- Lenstra, A. K.; Lenstra, H. W.; Lovász, László (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. ISSN 0025-5831. MR 0682664.
- Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.
- Kaltofen, Erich (1990), "Polynomial Factorization 1982-1986", in D. V. Chudnovsky; R. D. Jenks (eds.), Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics, 125, Marcel Dekker, Inc., CiteSeerX 10.1.1.68.7461
- Kaltofen, Erich (1992), "Polynomial Factorization 1987–1991" (PDF), Proceedings of Latin '92, Springer Lect. Notes Comput. Sci., 583, Springer, retrieved October 14, 2012
- Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), "Schemes for Deterministic Polynomial Factoring", Proc. ISSAC 2009: 191–198, arXiv:0804.1974, doi:10.1145/1576702.1576730, ISBN 9781605586090