The efficient calculation of powers of polynomials

Abstract

Suppose we are given a polynomial in (X1,..., Xr) in r ≥ 1 variables, let m bound the degree of p in all variables Xi, 1≤i≤r, and we wish to raise P to the nth power, n≫1. In a recent paper which compared the iterative versus the binary method it was shown that their respective computing times were O(m2rnr+1) versus O((mn) 2r) when using single precision arithmetic. In this paper a new algorithm is given whose computing time is shown to be O((mn) r+1). Also if we allow for polynomials with multiprecision integer coefficients, the new algorithm presented here will be faster by a factor of mr-1nr over the binary method and faster by a factor of mr-1 over the iterative method. Extensive empirical studies of all three methods show that this new algorithm will be superior for polynomials of even relatively small degree, thus guaranteeing a practical as well as a useful result.