TABLE OF CONTENTS Let u be a polynomial in Q[ x]. To find the irreducible factorization of u, first, we obtain the square-free factorization using the algorithm described in Section 9.1. Since each of the polynomials in the square-free factorization is monic and square-free, the problem is reduced to polynomials with these properties. Next, using Equation (9.24) on page 361, the problem is simplified again to primitive, square-free polynomials in Z[ x]. The last step in the process involves the factorization of these polynomials.
The algorithm described in this section obtains the irreducible factorization of a square-free, monic polynomial u in Z [x] by factoring a related polynomial in Z p [x] (for a suitable prime p) and then using the factors of this new polynomial to obtain the factors of u.
Notation Conventions. In this section, we perform polynomial operations in both Z [x] and Z m[ x]. To distinguish the operations in the two contexts, we adopt the following notation conventions.
For polynomial operations in Z[ x], we use the ordinary infix symbols for addition (+) and multiplication ( ).
For polynomial operations in Z m [x], we use the symbols ? m for addition and ? m for multiplication that were introduced in Section 2.3. In this section, m is either a prime number p (in which case Z p
