  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 time with respect to the sparsities of F, G and Q,
this is not yet sufficient to get a polynomial-time divisibility test in
general. Indeed, the sparsity of the quotient Q can be exponentially larger
than the ones of F and G. In the favorable case where the sparsity #Q of the
quotient is polynomial, the best known algorithm to compute Q has a non-linear
factor #G#Q in the complexity, which is not optimal.
  In this work, we are interested in the two aspects of this problem. First, we
propose a new randomized algorithm that computes the quotient of two sparse
polynomials when the division is exact. Its complexity is quasi-linear in the
sparsities of F, G and Q. Our approach relies on sparse interpolation and it
works over any finite field or the ring of integers. Then, as a step toward
faster divisibility testing, we provide a new polynomial-time algorithm when
the divisor has a specific shape. More precisely, we reduce the problem to
finding a polynomial S such that QS is sparse and testing divisibility by S can
be done in polynomial time. We identify some structure patterns in the divisor
G for which we can efficiently compute such a polynomial~S.
