Polynomial factorization

﻿
Polynomial factorization

In mathematics and computer algebra, polynomial factorization typically refers to factoring a polynomial into irreducible polynomials over a given field.

Formulation of the question

Other factorizations, such as square-free factorization exist, but the irreducible factorization, the most common, is the subject of this article.

Factorization depends strongly on the choice of field. For example, the fundamental theorem of algebra, which states that all polynomials with complex coefficients have complex roots, implies that a polynomial with integer coefficients can be completely reduced to linear factors over the complex field C.

On the other hand, such a polynomial may only be reducible to linear and quadratic factors over the real field R. Over the rational number field Q, it is possible that no factorization at all may be possible. From a more practical vantage point, the fundamental theorem is only an existence proof, and offers little insight into the common problem of actually finding the roots of a given polynomial.

Factoring over the integers and rationals

It can be shown that factoring over Q (the rational numbers) can be reduced to factoring over Z (the integers). This is a specific example of a more general case &mdash; factoring over a field of fractions can be reduced to factoring over the corresponding integral domain. This algebraic point goes by the name of Gauss's lemma.

The classic proof, due to Gauss, first factors a polynomial into its "content", a rational number, and its "primitive part", a polynomial whose coefficients are pure integers and share no common divisor among them. Any polynomial with rational coefficients can be factored in this way, using a content composed of the greatest common divisor of the numerators, and the least common multiple of the denominators. This factorization is unique.

For example,

:$10x^2 + 5x + 5 = 5 \left(2x^2 + x + 1\right) ,$

and

:$frac\left\{1\right\}\left\{3\right\}x^5 + frac\left\{7\right\}\left\{2\right\} x^2 + 2x + 1 = frac\left\{1\right\}\left\{6\right\} \left( 2x^5 + 21x^2 + 12x + 6\right)$

since $mathrm\left\{GCD\right\}\left(1,7,2,1\right)=1$ and $mathrm\left\{LCM\right\}\left(3,2\right)=6$.

Now, any polynomial with rational coefficients can be split into a content and a primitive polynomial, and in particular the factors of any factorization (over Q) of such a polynomial can also be so split. Since the content and the primitive polynomials are unique, and since the product of primitive polynomials is itself primitive, the primitive part of the polynomial must factor into the primitive parts of the factors. In particular, if a polynomial with integer coefficients can be factored at all, it can be factored into integer polynomials. So factoring a polynomial with rational coefficients can be reduced to finding integer factorizations of its primitive part.

Practical techniques

Currently the best techniques for factoring integer polynomials involve factoring over finite fields, but a simpler technique is usable for small polynomials (roughly less than tenth degree), if a computer is used. 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

:$f\left(x\right) = x^5 + x^4 + x^2 + x + 2$.

If this polynomial factors over Z, then at least one of its factors must be of degree two or less. We need three values to uniquely fit a second degree polynomial. We'll use $f\left(0\right) = 2$, $f\left(1\right) = 6$ and $f\left(-1\right) = 2$. Now, 2 can only factor as

: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

:1, 2, -1, or -2

at $x=0$, and likewise at $x=-1$. There are eight different ways to factor 6, so there are

:4×4×8 = 128

possible combinations, of which half can be discarded as the negatives of the other half, corresponding to 64 possible second degree integer polynomials which must be checked. These are the only possible integer polynomial factors of $f\left(x\right)$. Testing them exhaustively reveals that

:$g\left(x\right) = x^2+x+1$,

constructed from $g\left(0\right)=1$, $g\left(1\right)=2$ and $g\left(-1\right)=1$, factors $f\left(x\right)$.

("Van der Waerden", Sections 5.4 and 5.6)

Factoring over finite fields

See Berlekamp's algorithm and Cantor–Zassenhaus algorithm.

Factoring over algebraic extensions

We can factor a polynomial $p\left(x\right) in K \left[x\right]$, where $K$ is a finite field extension of $mathbb\left\{Q\right\}$. First we eliminate any repeated factors in $p\left(x\right)$ by taking greatest common divisors with its derivative. Next we write $L= K \left[x\right] /p\left(x\right)$ explicitly as an algebra over $mathbb\left\{Q\right\}$. We next pick a random element $alpha in L$. By the primitive element theorem, $alpha$ generates $L$ over $mathbb\left\{Q\right\}$ with high probability. If this is the case, we can compute the minimal polynomial, $q\left(y\right)in mathbb\left\{Q\right\} \left[y\right]$ of $alpha$ over $mathbb\left\{Q\right\}$. Factoring

:$q\left(y\right) = prod_\left\{i=1\right\}^\left\{n\right\} q_i\left(y\right)$

over $mathbb\left\{Q\right\} \left[y\right]$, we determine that

:$L = mathbb\left\{Q\right\} \left[alpha\right] = mathbb\left\{Q\right\} \left[y\right] /q\left(y\right) = prod_\left\{i=1\right\}^n mathbb\left\{Q\right\} \left[y\right] /q_i\left(y\right)$

(notice that $L$ is reduced since $p\left(x\right)$ is), where $alpha$ corresponds to the element $\left(y,y,ldots,y\right)$. Note that this is the unique decomposition of $L$ as a product fields. Hence this decomposition is the same as

:$prod_\left\{i=1\right\}^m K \left[x\right] /p_i\left(x\right)$

where

:$p\left(x\right) = prod_\left\{i=1\right\}^m p_i\left(x\right)$

is the factorization of $p\left(x\right)$ over $K \left[x\right]$. By writing $xin L$ and generators of $K$ as a polynomials in $alpha$, we can determine the embeddings of $x$ and $K$ into the components $mathbb\left\{Q\right\} \left[y\right] /q_i\left(y\right)=K \left[x\right] /p_i\left(x\right)$. By finding the minimal polynomial of $x$ in this ring, we have computed $p_i\left(x\right)$, and thus factored $p\left(x\right)$ over $K.$

Bibliography

* Van der Waerden, "Algebra" (1970), trans. Blum and Schulenberger, Frederick Ungar.

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Factorization — This article is about the mathematical concept. For other uses, see Factor and Integer factorization. A visual illustration of the polynomial x2 + cx + d = (x + a)(x + b) where… …   Wikipedia

• factorization — (Amer.) n. (Mathematics) resolution of an integer or polynomial into factors so that when multiplied together they give the integer or polynomial (also factorisation) …   English contemporary dictionary

• Polynomial ring — In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the …   Wikipedia

• Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… …   Wikipedia

• Polynomial expansion — In mathematics, an expansion of a product of sums expresses it as a sum of products by using the fact that multiplication distributes over addition. Expansions of polynomials are obtained by multiplying together their factors, which results in a… …   Wikipedia

• Square-free polynomial — In mathematics, a square free polynomial is a polynomial with no square factors, i.e, f in F [x] is square free if and only if b^2 mid f for every b in F [x] with non zero degree. This definition implies that no factors of higher order can exist …   Wikipedia

• List of polynomial topics — This is a list of polynomial topics, by Wikipedia page. See also trigonometric polynomial, list of algebraic geometry topics.Basics*Polynomial *Coefficient *Monomial *Polynomial long division *Polynomial factorization *Rational function *Partial… …   Wikipedia

• Schwartz-Zippel lemma and testing polynomial identities — Polynomial identity testing is the problem of determining whether a given multivariate polynomial is the0 polynomial or identically equal to 0. The input to the problem is an n variable polynomial over a fieldF. It can occur in the following… …   Wikipedia

• Irreducible polynomial — In mathematics, the adjective irreducible means that an object cannot be expressed as a product of at least two non trivial factors in a given set. See also factorization. For any field F , the ring of polynomials with coefficients in F is… …   Wikipedia

• Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia