Factoring sparse multivariate polynomials

摘要

This paper presents a probabilistic reduction for factoring polynomials from multivariate to the bivariate case, over an arbitrary (effectively computable) field. It uses an expected number of field operations (and certain random choices) that is polynomial in the size of sparse representations of input plus output, provided the number of irreducible factors is bounded. We thus obtain probabilistic polynomial-time factoring procedures over algebraic number fields and over finite fields. The reduction is based on an effective version of Hilbert's irreducibility theorem.