Extracting sparse factors from multivariate integral polynomials (Q1940925)

A algorithm for the following problem is presented. Given a sparse multivariate polynomial in several variables over the integers, and a bound \(t\), find all factors with at most \(t\) terms. The algorithm is probabilistic with expected polynomial time in \(t\), the number of variables, the height of the coefficients, the number of terms of the polynomial, and the degree of the polynomial.