An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial - Kaminski, Michael (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 q2 element 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 q2 have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.