An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
Date of Issue2013
School of Physical and Mathematical Sciences
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.
DRNTU::Science::Mathematics::Applied mathematics::Information theory
IEEE transactions on information theory