Factoring multivariate polynomials over the integers

Abstract

This paper gives an algorithm for finding the irreducible factors of any multivariate polynomial with integer coefficients. The algorithm begins by making substitutions for all but one of the variable. This univariate polynomial is then factored by a known method, which uses an algorithm of Berlekamp for factoring univariate polynomials over finite fields. After this factorization is done, the multivariate factors are recovered from the univariate ones by a kind of Hensel algorithm. A number of ideas are given which greatly speed the computation in some special cases.