Factoring Multivariate Polynomials Over the Integers

Publisher Website
Google Scholar
Abstract
An algorithm for the irreducible factorization of any multivariate polynomial over the integers is given. It is much faster than the classical method ascribed to Kronecker. The algorithm begins by making substitutions for all but one of the variables with selected integers, giving a polynomial in just one variable. This univariate polynomial is then factored by a known method, which uses an algorithm of Berlekamp for factoring univariate polynomials over finite fields. The multivariate factors are constructed from the univariate ones by a kind of Hensel algorithm. The procedure has been implemented in the algebraic manipulation systems MACSYMA and SCRATCHPAD. A number of machine examples with timing are included.

This publication has 5 references indexed in Scilit: