On the Computation of Powers of a Class of Polynomials

Abstract

A general class of polynomials is defined which includes as subcases sparse and dense polynomials. For any polynomial $P$ within this class a host of algorithms are analyzed for computing $P^{n}$. While the Homomorphism algorithm is superior on dense polynomials it is shown that for sufficiently sparse polynomials, iteration is more efficient. A simple rule that takes linear time is given for deciding when it is advisable to use either one of these algorithms. Keywords: Polynomial Powers, sparse polynomials, modular algorithms.