  Assessing that a sparse polynomial G divides another sparse polynomial F is
not yet known to admit a polynomial time algorithm. While computing the
quotient Q = F quo G can be done in polynomial time with respect to the
sparsities of F, G and Q, it 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 fields or the ring of integers. Then, as a step toward
faster divisibility testing, we provide a new polynomial time algorithm when
the divisor has some specific shapes. 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.
