Given a "black box" to evaluate an unknown rational polynomial f(x) at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. The computed sparsity t is absolutely minimal over any shifted power basis. The novelty of our algorithm is that the complexity is polynomial in the (sparse) representation size and in particular is logarithmic in the degree of f.

Our method combines previous celebrated results on sparse interpolation and computing sparsest shifts, and provides a way to handle polynomials with extremely high degree which are, in some sense, sparse in information. We give both an unconditional deterministic algorithm which is polynomial-time but has a rather high complexity, and a more practical probabilistic algorithm which relies on some unknown constants.