On the Computation of Powers of Sparse Polynomials

This paper examines the time for computing integer powers of a class of polynomials in one or several variables. A member f of the class of “sparse” polynomials can be characterized by the number of nonzero terms, t, in the representation of f. Where, for power 4, the most obvious methods result in multiplications, a method is presented which requires fewer than multiplications. This algorithm requires, for t » n » 1 about tⁿ/n! + O(t^{n ? 1} /(2(n ? 2)!)) multiplications, which is proved to be a lower-bound on the computation.