An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial

An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Kaminski, Michael, Xing, Chaoping
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2013
Subjects:
DRNTU::Science::Mathematics::Applied mathematics::Information theory
Online Access:https://hdl.handle.net/10356/98695
http://hdl.handle.net/10220/17481
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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.

Similar Items