Polynomial Factorization

Introduction

The Institute for Computational Mathematics (Kent State University, USA) offers a live demo of various symbolic computations including polynomial factorization.

But, this success does not mean at all that the problem is easy. In fact, the basic idea one may try (obtaining values of f(x) at some points and deducing from them the values of the coefficients in the factors) leads to an algorithm which does not work well at all : it is far too slow in practice. The idea which led to the present approach is due to Zassenhaus (1969). It uses elaborate tools from Number Theory whose connection with the factorization problem, routine now, was far from obvious at that time.

It is not possible to give here a complete overview of polynomial factorization and its history. The reader is referred to Kaltofen (1982), Knuth (1981), and Wang (1978, 1983). Described in vague terms, however, modern factorization algorithms work as follows. Assume, without loss of generality, that the given polynomial f(x) in Z[x] is primitive (content is 1) and squarefree (no repeated factors). Take a suitable prime p and reduce f modulo p to a polynomial f0 over the intergers mod p. Factor f0 over Z mod p into distinct irreducible factors (cf. Berlekamp (1967), Cantor-Zassenhaus (1981), Trevisan (1992)). Then ``lift'' these factors modulo increasingly larger modulus. Stop lifting when the modulus is large enough. Finally, recover the irreducible factors of f over the integers.

Bibtex data file