9.2 Irreducible Factorization: The Classical Approach

In this section we describe a simple (but highly inefficient) algorithm that obtains the irreducible factorization for polynomials in Q [x].

First, we show that it is sufficient to give a factorization algorithm for polynomials in the simpler domain Z [x]. Let

be a polynomial in Q [x], and let a _i and b _i be the numerator and denominator of the coefficients u _i. To obtain an equivalent factorization in Z [x], let M be the least common multiple ^[3] of the denominators,

and define the polynomial in Z [x]:

Then,

where pp (v) is a primitive polynomial in Z [x]. In addition, if pp (v) has the irreducible factorization (in Z [x])

then a factorization of u is given by

Although the polynomials p _i are not necessarily monic, this form is similar to the one obtained by the factor operator in most computer algebra systems.

Example 9.16

If u=(3/2) x ² ?3/8, then

We have u=(3/8) (4 x ² ?1)=(3/8) (2 x ?1)(2 x+1).

Before describing a factorization algorithm, we need to verify a technical point. Although each polynomial p _i in Equation (9.26) is irreducible in Z [x], we need to show that it is also irreducible in the larger domain Q [x]. This point is addressed in the following theorem.

Theorem 9.17. Let u be an...