On exact division and divisibility testing for sparse polynomials

Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray

No polynomial-time algorithm is known to test whether a sparse polynomial G divides another sparse polynomial $F$. While computing the quotient Q=F quo G can be done in polynomial…