In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer algebra, factorization of polynomials or polynomial factorization expresses a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
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 system
A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The ...
s.
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)
Nowadays, modern algorithms and computers can quickly factor
univariate polynomials of degree more than 1000 having coefficients with thousands of digits. For this purpose, even for factoring over the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s and
number fields, a fundamental step is a
factorization of a polynomial over a finite field.
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 Shepherdson 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 (that is, the field of the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
and the fields of the
integers modulo a prime number) and their
finitely generated field extension
In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ...
s. 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
and reductions:
* From the
multivariate
Multivariate may refer to:
In mathematics
* Multivariable calculus
* Multivariate function
* Multivariate polynomial
In computing
* Multivariate cryptography
* Multivariate division algorithm
* Multivariate interpolation
* Multivariate optical c ...
case to the
univariate case.
* From coefficients in a
purely transcendental extension
In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ...
to the multivariate case over the ground field (see
below
Below may refer to:
*Earth
* Ground (disambiguation)
*Soil
*Floor
* Bottom (disambiguation)
*Less than
*Temperatures below freezing
*Hell or underworld
People with the surname
*Ernst von Below (1863–1955), German World War I general
*Fred Below ...
).
* From coefficients in an algebraic extension to coefficients in the ground field (see
below
Below may refer to:
*Earth
* Ground (disambiguation)
*Soil
*Floor
* Bottom (disambiguation)
*Less than
*Temperatures below freezing
*Hell or underworld
People with the surname
*Ernst von Below (1863–1955), German World War I general
*Fred Below ...
).
* From rational coefficients to integer coefficients (see
below
Below may refer to:
*Earth
* Ground (disambiguation)
*Soil
*Floor
* Bottom (disambiguation)
*Less than
*Temperatures below freezing
*Hell or underworld
People with the surname
*Ernst von Below (1863–1955), German World War I general
*Fred Below ...
).
* From integer coefficients to coefficients in a prime field with ''p'' elements, for a well chosen ''p'' (see
below
Below may refer to:
*Earth
* Ground (disambiguation)
*Soil
*Floor
* Bottom (disambiguation)
*Less than
*Temperatures below freezing
*Hell or underworld
People with the surname
*Ernst von Below (1863–1955), German World War I general
*Fred Below ...
).
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.
For example,
:
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.
For example,
:
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''.
Square-free factorization
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
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
(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 ''x''
''p'' 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.
Classical methods
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.
The two methods that follow start from a
univariate polynomial with integer coefficients for finding factors that are also polynomials with integer coefficients.
Obtaining linear factors
All linear factors with
rational coefficients can be found using the
rational root test. If the polynomial to be factored is
, then all possible linear factors are of the form
, where
is an integer factor of
and
is an integer factor of
. All possible combinations of integer factors can be tested for validity, and each valid one can be factored out using
polynomial long division
In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, bec ...
. If the original polynomial is the product of factors at least two of which are of degree 2 or higher, this technique only provides a partial factorization; otherwise the factorization is complete. In particular, if there is exactly one non-linear factor, it will be the polynomial left after all linear factors have been factorized out. In the case of a
cubic polynomial, if the cubic is factorizable at all, the rational root test gives a complete factorization, either into a linear factor and an irreducible quadratic factor, or into three linear factors.
Kronecker's method
Kronecker's method is aimed to factor
univariate polynomials with integer coefficients into polynomials with integer coefficients.
The method uses the fact that evaluating integer polynomials at integer values must produce integers. That is, if
is a polynomial with integer coefficients, then
is an integer as soon as is an integer. There are only a finite number of possible integer values for a factor of . So, if
is a factor of
the value of
must be one of the factors of
If one searches for all factors of a given degree , one can consider
values,
for , which give a finite number of possibilities for the
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
Each
has a finite number of divisors
, and, each
-tuple where the
entry is a divisor of
, that is, a tuple of the form
, produces a unique polynomial of degree at most
, which can be computed by
polynomial interpolation. Each of these polynomials can be tested for being a factor by
polynomial division. Since there were finitely many
and each
has finitely many divisors, there are finitely many such tuples. So, an exhaustive search allows finding all factors of degree at most .
For example, consider
:
.
If this polynomial factors over Z, then at least one of its factors
must be of degree two or less, so
is uniquely
determined by three values. Thus, we compute three values
,
and
. If one of these values is 0, we have a linear factor. If the values are nonzero, we can list the possible factorizations for each. 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
:''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
as possible factors of
. Testing them exhaustively reveals that
:
constructed from (''g''(0), ''g''(1), ''g''(−1)) = (1,3,1) factors
.
Dividing ''f''(''x'') by ''p''(''x'') gives the other factor
, so that
.
Now one can test recursively to find factors of ''p''(''x'') and ''q''(''x''), in this case using the rational root test. It turns out they are both irreducible, so the irreducible factorization of ''f''(''x'') is:
:
Modern methods
Factoring over finite fields
Factoring univariate polynomials over the integers
If
is a univariate polynomial over the integers, assumed
to be
content-free
and
square-free, one starts by computing a bound
such that any factor
has coefficients of
absolute value bounded by
. This way, if
is
an integer larger than
, and if
is known modulo
, then
can be reconstructed from its image mod
.
The
Zassenhaus algorithm proceeds as follows. First, choose a prime
number
such that the image of
mod
remains
square-free, and of the same degree as
.
Then factor
mod
. This produces integer polynomials
whose product matches
mod
. Next, apply
Hensel lifting; this updates the
in such a way that their product matches
mod
, where
is large enough that
exceeds
: thus each
corresponds to a well-defined integer polynomial. Modulo
, the polynomial
has
factors (up to units): the products of all subsets of
mod
. These factors modulo
need not correspond to "true" factors of
in