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

id	sg-ntu-dr.10356-98695
record_format	dspace
spelling	sg-ntu-dr.10356-986952020-03-07T12:37:10Z An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial Kaminski, Michael Xing, Chaoping School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Applied mathematics::Information theory 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. 2013-11-08T06:21:22Z 2019-12-06T19:58:33Z 2013-11-08T06:21:22Z 2019-12-06T19:58:33Z 2013 2013 Journal Article Kaminski, M., & Xing, C. (2013). An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial. IEEE transactions on information theory, 59(10), 6845-6850. https://hdl.handle.net/10356/98695 http://hdl.handle.net/10220/17481 10.1109/TIT.2013.2272072 en IEEE transactions on information theory
institution	Nanyang Technological University
building	NTU Library
country	Singapore
collection	DR-NTU
language	English
topic	DRNTU::Science::Mathematics::Applied mathematics::Information theory
spellingShingle	DRNTU::Science::Mathematics::Applied mathematics::Information theory Kaminski, Michael Xing, Chaoping An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
description	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.
author2	School of Physical and Mathematical Sciences
author_facet	School of Physical and Mathematical Sciences Kaminski, Michael Xing, Chaoping
format	Article
author	Kaminski, Michael Xing, Chaoping
author_sort	Kaminski, Michael
title	An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
title_short	An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
title_full	An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
title_fullStr	An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
title_full_unstemmed	An upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
title_sort	upper bound on the complexity of multiplication of polynomials modulo a power of an irreducible polynomial
publishDate	2013
url	https://hdl.handle.net/10356/98695 http://hdl.handle.net/10220/17481
_version_	1681039005679878144

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

Similar Items