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 条
  • [31] Error Correcting Codes via Reversible Cellular Automata Over Finite Fields
    Koroglu, Mehmet E.
    Siap, Irfan
    Akin, Hasan
    ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING, 2014, 39 (03) : 1881 - 1887
  • [32] Bounds on Subspace Codes Based on Orthogonal Space Over Finite Fields of Characteristic 2
    Wang, Gang
    Niu, Min-Yao
    Fu, Fang-Wei
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2019, 30 (05) : 735 - 757
  • [33] Relationships of bounds for sizes of subspace codes in singular linear spaces over finite fields
    Wang, Gang
    Niu, Min-Yao
    Fu, Fang-Wei
    ARS COMBINATORIA, 2020, 149 : 137 - 151
  • [34] A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
    Woodruff, David P.
    APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2010, 6302 : 766 - 779
  • [35] A new construction of quantum codes from quasi-cyclic codes over finite fields
    Biswas, Soumak
    Bhaintwal, Maheshanand
    INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2023, 54 (02) : 375 - 388
  • [36] MDS Constacyclic Codes of Prime Power Lengths Over Finite Fields and Construction of Quantum MDS Codes
    Dinh, Hai Q.
    ElDin, Ramy Taki
    Nguyen, Bac T.
    Tansuchat, Roengchai
    INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 2020, 59 (10) : 3043 - 3078
  • [37] RANK-DEFICIENT REPRESENTATIONS IN THE THETA CORRESPONDENCE OVER FINITE FIELDS ARISE FROM QUANTUM CODES
    Montealegre-Mora, Felipe
    Gross, David
    REPRESENTATION THEORY, 2021, 25 : 193 - 223
1234