TABLE OF CONTENTS The goal of this chapter is the complete description of a modern algorithm for the factorization of polynomials in Q [x] in terms of irreducible polynomials.
In Section 9.1 we describe an algorithm that obtains a partial factorization of a polynomial. The algorithm can separate factors of different multiplicities as in
but is unable to separate factors of the same multiplicity as in
This factorization is important, however, because it reduces the factorization problem to polynomials without multiple factors. In Section 9.2 we describe the classical approach to factorization, which is known as Kronecker's algorithm. This algorithm is primarily of historical interest because it is much too slow to be used in practice. In Section 9.3 we describe an algorithm that factors polynomials in Z p [x]. Although this algorithm is important in its own right, it is included here because it plays a role in the modern approach for factorization in Q [x]. Finally, in Section 9.4 we describe a modern factorization algorithm, known as the Berlekamp-Hensel algorithm, which uses a related factorization in Z p [x] together with a lifting algorithm to obtain the factorization in Q [x].
The efficient factorization of polynomials is a difficult computational problem. For this reason, both the mathematical and computational techniques in this chapter are more involved than those in previous chapters.
