  Consider a sparse polynomial in several variables given explicitly as a sum
of non-zero terms with coefficients in an effective field. In this paper, we
present several algorithms for factoring such polynomials and related tasks
(such as gcd computation, square-free factorization, content-free
factorization, and root extraction). Our methods are all based on sparse
interpolation, but follow two main lines of attack: iteration on the number of
variables and more direct reductions to the univariate or bivariate case. We
present detailed probabilistic complexity bounds in terms of the complexity of
sparse interpolation and evaluation.
