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 条
  • [21] On the rank of Hankel matrices over finite fields
    Dwivedi, Omesh Dhar
    Grinberg, Darij
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 641 : 156 - 181
  • [22] Varieties over finite fields: quantitative theory
    Vladut, S. G.
    Nogin, D. Yu.
    Tsfasman, M. A.
    RUSSIAN MATHEMATICAL SURVEYS, 2018, 73 (02) : 261 - 322
  • [23] Low-Complexity and High-Throughput Number Theoretic Transform Architecture for Polynomial Multiplication in Homomorphic Encryption
    Sutisna, Nana
    Brillianshah, Elkhan J.
    Syafalnin, Infall
    Hasanuddin, M. Ogin
    Adiono, Trio
    Juhana, Tutun
    2024 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, ISCAS 2024, 2024,
  • [24] Computing factors of cyclotomic polynomials over finite fields
    Sehrawat, Deepak
    Singh, Manjit
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2025, 61 (03)
  • [25] Composed products and factors of cyclotomic polynomials over finite fields
    Tuxanidy, Aleksandr
    Wang, Qiang
    DESIGNS CODES AND CRYPTOGRAPHY, 2013, 69 (02) : 203 - 231
  • [26] Composed products and factors of cyclotomic polynomials over finite fields
    Aleksandr Tuxanidy
    Qiang Wang
    Designs, Codes and Cryptography, 2013, 69 : 203 - 231
  • [27] A new architecture for a parallel finite field multiplier with low complexity based on composite fields
    Paar, C
    IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (07) : 856 - 861
  • [28] Error-correcting codes in attenuated space over finite fields
    Gao, You
    Wang, Gang
    FINITE FIELDS AND THEIR APPLICATIONS, 2015, 33 : 103 - 117
  • [29] Group structure on projective spaces and cyclic codes over finite fields
    Lachaud, G
    Lucien, I
    Mercier, DJ
    Rolland, R
    FINITE FIELDS AND THEIR APPLICATIONS, 2000, 6 (02) : 119 - 129
  • [30] Error Correcting Codes via Reversible Cellular Automata Over Finite Fields
    Mehmet E. Koroglu
    Irfan Siap
    Hasan Akın
    Arabian Journal for Science and Engineering, 2014, 39 : 1881 - 1887
1234