An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial

作者：Kaminski Michael^*; Xing Chaoping

来源：IEEE Transactions on Information Theory, 2013, 59(10): 6845-6850.

DOI：10.1109/TIT.2013.2272072

• Algebraic function fields
• bilinear algorithms
• finite fields
• polynomial multiplication
• the Garcia-Stichtenoth tower

Let mu(q2)(n, k)denote the minimum number of multiplications required to compute the coefficients of the product of two degree nk - 1 polynomials modulo the kth power of an irreducible polynomial of degree n over the q(2) element field F-q2. It is shown that for all odd q and all n = 1,2,..., lim inf(k -%26gt;infinity) mu(q2)(n, k)/kn %26lt;= 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 F-q2 over have places of all degrees and apply a Chudnovsky like algorithm for multiplication of polynomials modulo a power of an irreducible polynomial.

• 出版日期2013-10
• 单位南阳理工学院