Nondivisibility of Sparse Polynomials is in NP Under the Extended Riemann Hypothesis

Symbolic manipulation of sparse polynomials, given as lists of exponents and nonzero coefficients, appears to be much more complicated than dealing with polynomials in dense encoding (see e.g. [GKS 90, KT 88, P 77a, P 77b]). The first results in this direction are due to Plaisted [P 77a, P 77B], who proved in particular the NP-completeness of divisibility of a polynomial x sup n -1 by a product of sparse polynomials.