A lower bound on the complexity of polynomial multiplication over finite fields

被引：6
|
作者：
Kaminski, M [1 ]
机构：
[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel
来源：
SIAM JOURNAL ON COMPUTING | 2005年 / 34卷 / 04期
关键词：
polynomial multiplication; quadratic algorithms; linear recurring sequences; Hankel matrices; error-correcting codes;
D O I：
10.1137/S0097539704442118
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
It is shown that computing the coefficients of the product of two degree-n polynomials over a q-element field by means of a quadratic algorithm requires at least (3 + (q-1)(2)/ q(5)+( q- 1)(3)) n - o( n) multiplications.
引用
收藏
页码：960 / 992
页数：33
相关论文
共 37 条
  • [1] Polynomial multiplication over finite fields: From quadratic to straight-line complexity
    Bshouty, Nader H.
    Kaminski, Michael
    COMPUTATIONAL COMPLEXITY, 2006, 15 (03) : 252 - 262
  • [2] Polynomial multiplication over finite fields: from quadratic to straight-line complexity
    Nader H. Bshouty
    Michael Kaminski
    computational complexity, 2006, 15 : 252 - 262
  • [3] Faster Polynomial Multiplication over Finite Fields
    Harvey, David
    van der Hoeven, Joris
    Lecerf, Gregoire
    JOURNAL OF THE ACM, 2017, 63 (06)
  • [4] Polynomial multiplication over binary finite fields: new upper bounds
    De Piccoli, Alessandro
    Visconti, Andrea
    Rizzo, Ottavio Giulio
    JOURNAL OF CRYPTOGRAPHIC ENGINEERING, 2020, 10 (03) : 197 - 210
  • [5] Polynomial multiplication over binary finite fields: new upper bounds
    Alessandro De Piccoli
    Andrea Visconti
    Ottavio Giulio Rizzo
    Journal of Cryptographic Engineering, 2020, 10 : 197 - 210
  • [6] Polynomial Multiplication over Binary Fields Using Charlier Polynomial Representation with Low Space Complexity
    Akleylek, Sedat
    Cenk, Murat
    Ozbudak, Ferruh
    PROGRESS IN CRYPTOLOGY - INDOCRYPT 2010, 2010, 6498 : 227 - 237
  • [7] A LOWER BOUND FOR THE MULTIPLICATION OF POLYNOMIALS MODULO A POLYNOMIAL
    BSHOUTY, NH
    INFORMATION PROCESSING LETTERS, 1992, 41 (06) : 321 - 326
  • [8] Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
    Harvey, David
    van Der Hoeven, Loris
    JOURNAL OF COMPLEXITY, 2019, 54
  • [9] Polynomial Multiplication over Finite Fields in Time O(n log n)
    Harvey, David
    van der Hoeven, Joris
    JOURNAL OF THE ACM, 2022, 69 (02)
  • [10] 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
1234