An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial

Let μ_q²(n,k) denote the minimum number of multiplications required to compute the coefficients of the product of two degree n k - 1 polynomials modulo the kth power of an irreducible polynomial of degree n over the q² element field BBF q². It is shown that for all odd q and all n = 1,2,..., liminfk → ∞[( μ_q²(n,k))/ k n] ≤ 2 (1 + [ 1/( q - 2)] ). For the proof of this upper bound, we show that for an odd prime power q, all algebraic function fields in the Garcia-Stichtenoth tower over BBF q² have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.