An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial
Michael Kaminski, Chaoping Xing · IEEE Transactions on Information Theory · 2013
Let μq2(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 q2element field \BBF q2. It is shown that for all odd q and all n = 1,2,..., liminfk → ∞[( μq2(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 q2have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.