Résumé
We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Let f ∈ Z[x] be an unknown polynomial and s, D be bounds on its total bit-length and degree, our new interpolation algorithm returns f with high probability using Õ(s log D) bit operations and O(s log D log s) black box evaluation. For polynomial multiplication, assuming the bit-length s of the product is not given, our algorithm has an expected running time of Õ(s log D), whereas previous methods for (resp.) dense or sparse arithmetic have at least Õ(sD) or Õ s 2 bit complexity.