Factorization of Polynomials

In this talk we shall discuss both the theory and the practice, with a certain emphasis on the latter, of factorizing polynomials over the rationals. The talk naturally splits into two parts: dealing with univariate polynomials, and dealing with multivariate polynomials. While there is a similarity in theory, the topics are really quite separate.

Historically, algorithms for factorizing polynomials have been known for over 200 years, but only in the last 30 years have ``modern'' techniques been available. The difference is striking: nowadays a good implementation can determine the factors of a univariate polynomial of degree 50 with 100-digit coefficients in a fraction of a second on a workstation, whereas with the ``old'' methods the combined power of all the computers in the world would probably take millions of years to find its factorization.

More recently, methods with low complexity have been discovered, though generally they are not competitive against the common Berlekamp-Zassenhaus strategy. We shall concentrate on this latter approach as it is currently the most relevant for actually computing factors.

Why is it interesting to factorize polynomials? Most polynomials are irreducible, so if a polynomial factorizes it is ``special''. For instance, during the computation of a Groebner basis we can exploit the reducibility of a polynomial to replace one big computational problem by a few smaller ones. Frequently factorization has been dismissed as ``too expensive''; this is no longer justified.

In the first part we shall give an overview of the Berlekamp-Zassenhaus algorithm, and some of the theory behind it. We shall also cover some aspects of its realisation in CoCoA, an implementation competitive with other systems.

In the second part we shall give an overview of the analogous algorithm for factorizing multivariate polynomials describing aspects of both theory and practice.