Factorization


In mathematics, factorization or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, is a factorization of the integer, and is a factorization of the polynomial.
Factorization is not usually considered meaningful within number systems possessing division, such as the real or complex numbers, since any can be trivially written as whenever is not zero. However, a meaningful factorization for a rational number or a rational function can be obtained by writing it in lowest terms and separately factoring its numerator and denominator.
Factorization was first considered by ancient Greek mathematicians in the case of integers. They proved the fundamental theorem of arithmetic, which asserts that every positive integer may be factored into a product of prime numbers, which cannot be further factored into integers greater than 1. Moreover, this factorization is unique up to the order of the factors. Although integer factorization is a sort of inverse to multiplication, it is much more difficult algorithmically, a fact which is exploited in the RSA cryptosystem to implement public-key cryptography.
Polynomial factorization has also been studied for centuries. In elementary algebra, factoring a polynomial reduces the problem of finding its roots to finding the roots of the factors. Polynomials with coefficients in the integers or in a field possess the unique factorization property, a version of the fundamental theorem of arithmetic with prime numbers replaced by irreducible polynomials. In particular, a univariate polynomial with complex coefficients admits a unique factorization into linear polynomials: this is a version of the fundamental theorem of algebra. In this case, the factorization can be done with root-finding algorithms. The case of polynomials with integer coefficients is fundamental for computer algebra. There are efficient computer algorithms for computing factorizations within the ring of polynomials with rational number coefficients.
A commutative ring possessing the unique factorization property is called a unique factorization domain. There are number systems, such as certain rings of algebraic integers, which are not unique factorization domains. However, rings of algebraic integers satisfy the weaker property of Dedekind domains: ideals factor uniquely into prime ideals.
Factorization may also refer to more general decompositions of a mathematical object into the product of smaller or simpler objects. For example, every function may be factored into the composition of a surjective function with an injective function. Matrices possess many kinds of matrix factorizations. For example, every matrix has a unique LUP factorization as a product of a lower triangular matrix with all diagonal entries equal to one, an upper triangular matrix, and a permutation matrix ; this is a matrix formulation of Gaussian elimination.

Integers

By the fundamental theorem of arithmetic, every integer greater than 1 has a unique factorization into prime numbers, which are those integers which cannot be further factorized into the product of integers greater than one.
For computing the factorization of an integer, one needs an algorithm for finding a divisor of or deciding that is prime. When such a divisor is found, the repeated application of this algorithm to the factors and gives eventually the complete factorization of.
For finding a divisor of, if any, it suffices to test all values of such that and. In fact, if is a divisor of such that, then is a divisor of such that.
If one tests the values of in increasing order, the first divisor that is found is necessarily a prime number, and the cofactor cannot have any divisor smaller than. For getting the complete factorization, it suffices thus to continue the algorithm by searching a divisor of that is not smaller than and not greater than.
There is no need to test all values of for applying the method. In principle, it suffices to test only prime divisors. This needs to have a table of prime numbers that may be generated for example with the sieve of Eratosthenes. As the method of factorization does essentially the same work as the sieve of Eratosthenes, it is generally more efficient to test for a divisor only those numbers for which it is not immediately clear whether they are prime or not. Typically, one may proceed by testing 2, 3, 5, and the numbers > 5, whose last digit is 1, 3, 7, 9 and the sum of digits is not a multiple of 3.
This method works well for factoring small integers, but is inefficient for larger integers. For example, Pierre de Fermat was unable to discover that the 6th Fermat number
is not a prime number. In fact, applying the [|above] method would require more than, for a number that has 10 decimal digits.
There are more efficient factoring algorithms. However they remain relatively inefficient, as, with the present state of the art, one cannot factorize, even with the more powerful computers, a number of 500 decimal digits that is the product of two randomly chosen prime numbers. This ensures the security of the RSA cryptosystem, which is widely used for secure internet communication.

Example

For factoring into primes:
Manipulating expressions is the basis of algebra. Factorization is one of the most important methods for expression manipulation for several reasons. If one can put an equation in a factored form, then the solving problem splits into two independent problems and. When an expression can be factored, the factors are often much simpler, and may, therefore, offer some insight on the problem. For example,
having 16 multiplications, 4 subtractions and 3 additions, may be factored into the much simpler expression
with only two multiplications and three subtractions. Moreover, the factored form gives immediately the roots x = a,b,c of the polynomial in represented by these expressions.
On the other hand, factorization is not always possible, and when it is possible, the factors are not always simpler. For example, can be factored into two irreducible factors and.
Various methods have been developed for finding factorizations; some are described [|below].
Solving algebraic equations may be viewed as a problem of factorization. In fact, the fundamental theorem of algebra can be stated as follows. Every polynomial in of degree with complex coefficients may be factorized into linear factors for, where the s are the roots of the polynomial. Even though the structure of the factorization is known in these cases, the
s generally cannot be computed in terms of radicals, by the Abel–Ruffini theorem. In most cases, the best that can be done is computing approximate values of the roots with a root-finding algorithm.

History of factorization of expressions

The systematic use of algebraic manipulations for simplifying expressions ) may be dated to 9th century, with al-Khwarizmi's book The Compendious Book on Calculation by Completion and Balancing, which is titled with two such types of manipulation. However, even for solving quadratic equations, factoring method was not used before Harriot’s work published in 1631, ten years after his death.
In his book Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas, Harriot drew, in a first section, tables for addition, subtraction, multiplication and division of monomials, binomials, and trinomials. Then, in a second section, he set up the equation, and showed that this matches the form of multiplication he had previously provided, giving the factorization .

General methods

The following methods apply to any expression that is a sum, or that may be transformed into a sum. Therefore, they are most often applied to polynomials, though they also may be applied when the terms of the sum are not monomials, that is, the terms of the sum are a product of variables and constants.

Common factor

It may occur that all terms of a sum are products and that some factors are common to all terms. In this case, the distributive law allows factoring out this common factor. If there are several such common factors, it is worth to divide out the greatest such common factor. Also, if there are integer coefficients, one may factor out the greatest common divisor of these coefficients.
For example,
since 2 is the greatest common divisor of 6, 8, and 10, and divides all terms.

Grouping

Grouping terms may allow using other methods for getting a factorization.
For example, to factor
one may remark that the first two terms have a common factor, and the last two terms have the common factor. Thus
Then a simple inspection shows the common factor, leading to the factorization
In general, this works for sums of 4 terms that have been obtained as the product of two binomials. Although not frequently, this may work also for more complicated examples.

Adding and subtracting terms

Sometimes, some term grouping lets appear a part of a [|recognizable pattern]. It is then useful to add terms for completing the pattern, and subtract them for not changing the value of the expression.
A typical use of this is the completing the square method for getting quadratic formula.
Another example is the factorization of If one introduces the imaginary square root of –1, commonly denoted, then one has a difference of squares
However, one may also want a factorization with real number coefficients. By adding and subtracting and grouping three terms together, one may recognize the square of a binomial:
Subtracting and adding also yields the factorization
These factorizations work not only over the complex numbers, but also over any field, where either -1, 2 or –2 is a square. In a finite field, the product of two non-squares is a square; this implies that the polynomial which is irreducible over the integers, is reducible modulo every prime number. For example,

Recognizable patterns

Many identities provide an equality between a sum and a product. The above methods may be used for letting the sum side of some identity appear in an expression, which may therefore be replaced by a product.
Below are identities whose left-hand sides are commonly used as patterns (this means that the variables and that appear in these identities may represent any subexpression of the expression that has to be factorized.

Roots of unity

The th roots of unity are the complex numbers each of which is a root of the polynomial They are thus the numbers
for
It follows that for any two expressions and, one has:
If and are real expressions, and one wants real factors, one has to replace every pair of complex conjugate factors by its product. As the complex conjugate of is and
one has the following real factorizations ; however, these radical expressions are too complicated to be used, except for low values of. For example,
Often one wants a factorization with rational coefficients. Such a factorization involves cyclotomic polynomials. To express rational factorizations of sums and differences or powers, we need a notation for the homogenization of a polynomial: if its homogenization is the bivariate polynomial Then, one has
where the products are taken over all divisors of, or all divisors of that do not divide, and is the th cyclotomic polynomial.
For example,
since the divisors of 6 are 1, 2, 3, 6, and the divisors of 12 that do not divide 6 are 4 and 12.

Polynomials

For polynomials, factorization is strongly related with the problem of solving algebraic equations. An algebraic equation has the form
where
where is a polynomial in, such that
A solution of this equation is a value of such that
If
is a factorization of as a product of two polynomials, then the roots of are the union of the roots of and the roots of. Thus solving is reduced to the simpler problems of solving and.
Conversely, the factor theorem asserts that, if is a root of, then may be factored as
where is the quotient of Euclidean division of by.
If the coefficients of are real or complex numbers, the fundamental theorem of algebra asserts that has a real or complex root. Using the factor theorem recursively, it results that
where are the real or complex roots of, with some of them possibly repeated. This complete factorization is unique up to the order of the factors.
If the coefficients of are real, one generally wants a factorization where factors have real coefficients. In this case, the complete factorization may have some factors that have the degree two. This factorization may easily be deduced from the above complete factorization. In fact, if is a non-real root of, then its complex conjugate is also a root of. So, the product
is a factor of that has real coefficients. This grouping of non-real factors may be continued until getting eventually a factorization with real factors that are polynomials of degrees one or two.
For computing these real or complex factorizations, one has to know the roots of the polynomial. In general, they may not be computed exactly, and only approximative values of the roots may be obtained. See Root-finding algorithm for a summary of the numerous efficient algorithms that have been designed for this purpose.
Most algebraic equations that are encountered in practice have integer or rational coefficients, and one may want a factorization with factors of the same kind. The fundamental theorem of arithmetic may be generalized to this case. That is, polynomials with integer or rational coefficients have the unique factorization property. More precisely, every polynomial with rational coefficients may be factorized in a product
where is a rational number and are non-constant polynomials with integer coefficients that are irreducible and primitive; this means that none of the may be written as the product two polynomials that are neither 1 nor –1. Moreover, this factorization is unique up to the order of the factors and the multiplication by –1 of an even number of factors.
There are efficient algorithms for computing this factorization, which are implemented in most computer algebra systems. See Factorization of polynomials. Unfortunately, for a paper-and-pencil computation, these algorithms are too complicated to be usable. Besides the general heuristics that are described above, only a few methods are available in this case, which generally work only for polynomials of low degree, with few nonzero coefficients. The main such methods are described in next subsections.

Primitive part–content factorization

Every polynomial with rational coefficients, may be factorized, in a unique way, as the product of a rational number and a polynomial with integer coefficients, which is primitive, and has a positive leading coefficient. For example:
In this factorization, the rational number is called the content, and the primitive polynomial is the primitive part. The computation of this factorization may be done as follows: firstly, reduce all coefficients to a common denominator, for getting the quotient by an integer of a polynomial with integer coefficients. Then one divides out the greater common divisor of the coefficients of this polynomial for getting the primitive part, the content being Finally, if needed, one changes the signs of and all coefficients of the primitive part.
This factorization may produce a result that is larger than the original polynomial, but, even when this is the case, the primitive part is generally easier to manipulate for further factorization.

Using the factor theorem

The factor theorem states that, if is a root of a polynomial
, then there is a factorization
where
with and
for.
This may be useful when, either by inspection, or by using some external information, one knows a root of the polynomial. For computing, instead of using the above formula, one may also use polynomial long division or synthetic division.
For example, for the polynomial one may easily see that the sum of its coefficients is 1. Thus is a root. As, and one has

Rational roots

Searching rational roots of a polynomial makes sense only for polynomials with rational coefficients. Primitive part-content factorization reduces the problem of searching for rational roots to the case of polynomials with integer coefficients such that the greatest common divisor of the coefficients is one.
If is a rational root of such a polynomial
the factor theorem shows that one has a factorization
where both factors have integer coefficients.
Comparing the coefficients of degree and the constant coefficients in the above equality shows that, if is a rational root in reduced form, then is a divisor of and is a divisor of Therefore, there is a finite number of possibilities for and, which can be systematically examined.
For example, if the polynomial
has a rational root with, then must divide 6; that is and must divide 2, that is Moreover, if, all terms of the polynomial are negative, and, therefore, a root cannot be negative. That is, one must have
A direct computation shows that is a root, and that there is no other rational root. Applying the factor theorem leads finally to the factorization

AC method

For quadratic polynomials, the above method may be adapted, leading to the so-called ac method of factorization.
Consider the quadratic polynomial
with integer coefficients. If it has a rational root, its denominator must divide evenly. So, it may be written as a possibly reducible fraction By Vieta's formulas, the other root is
with
Thus the second root is also rational, and the second Vieta's formula gives
that is
Checking all pairs of integers whose product is gives the rational roots, if any.
For example, let consider the quadratic polynomial
Inspection of the factors of leads to, giving the two roots
and the factorization

Using formulas for polynomial roots

Any univariate quadratic polynomial can be factored using the quadratic formula:
where and are the two roots of the polynomial.
If are all real, the factors are real if and only if the discriminant is non-negative. Otherwise, the quadratic polynomial cannot be factorized into non-constant real factors.
The quadratic formula is valid when the coefficients belong to any field of characteristic different from two, and, in particular, for coefficients in a finite field with an odd number of elements.
There are also formulas for roots of cubic and quartic polynomials, which are, in general, too complicated for practical use. The Abel–Ruffini theorem shows that there are no general root formulas in terms of radicals for polynomials of degree five or higher.

Using relations between roots

It may occur that one knows some relationship between the roots of a polynomial and its coefficients. Using this knowledge may help factoring the polynomial and finding its roots. Galois theory is based on a systematic study of the relations between roots and coefficients, that include Vieta's formulas.
Here, we consider the simpler case where two roots
and of a polynomial satisfy the relation
where is a polynomial.
This implies that is a common root of and Its is therefore a root of the greatest common divisor of these two polynomials. It follows that this greatest common divisor is a non constant factor of Euclidean algorithm for polynomials allows computing this greatest common factor.
For example, if one know or guess that:
has two roots that sum to zero, one may apply Euclidean algorithm to and The first division step consists in adding to giving the remainder of
Then, dividing by gives zero as a new remainder, and as a quotient, leading to the complete factorization

Unique factorization domains

The integers and the polynomials over a field share the property of unique factorization, that is, every nonzero element may be factored into a product of an invertible element and a product of irreducible elements, and this factorization is unique up to rearranging the factors and shifting units among the factors. Integral domains which share this property are called unique factorization domains.
Greatest common divisors exist in UFDs, and conversely, every integral domain in which greatest common divisors exist is an UFD. Every principal ideal domain is an UFD.
A Euclidean domain is an integral domain on which is defined a Euclidean division similar to that of integers. Every Euclidean domain is a principal ideal domain, and thus a UFD.
In a Euclidean domain, Euclidean division allows defining a Euclidean algorithm for computing greatest common divisors. However this does not imply the existence of a factorization algorithm. There is an explicit example of a field such that there cannot exist any factorization algorithm in the Euclidean domain of the univariate polynomials over.

Ideals

In algebraic number theory, the study of Diophantine equations led mathematicians, during 19th century, to introduce generalizations of the integers called algebraic integers. The first ring of algebraic integers that have been considered were Gaussian integers and Eisenstein integers, which share with usual integers the property of being principal ideal domains, and have thus the unique factorization property.
Unfortunately, it soon appeared that most rings of algebraic integers are not principal and do not have unique factorization. The simplest example is in which
and all these factors are irreducible.
This lack of unique factorization is a major difficulty for solving Diophantine equations. For example, many wrong proofs of Fermat's Last Theorem were based on the implicit supposition of unique factorization.
This difficulty was resolved by Dedekind, who proved that the rings of algebraic integers have unique factorization of ideals: in these rings, every ideal is a product of prime ideals, and this factorization is unique up the order of the factors. The integral domains that have this unique factorization property are now called Dedekind domains. They have many nice properties that make them fundamental in algebraic number theory.

Matrices

Matrix rings are non-commutative and have no unique factorization: there are, in general, many ways of writing a matrix as a product of matrices. Thus, the factorization problem consists of finding factors of specified types. For example, the LU decomposition gives a matrix as the product of a lower triangular matrix by an upper triangular matrix. As this is not always possible, one generally considers the "LUP decomposition" having a permutation matrix as its third factor.
See Matrix decomposition for the most common types of matrix factorizations.
A logical matrix represents a binary relation, and matrix multiplication corresponds to composition of relations. Decomposition of a relation through factorization serves to profile the nature of the relation, such as a difunctional relation.