Faster polynomial multiplication over finite fields using cyclotomic coefficient rings

被引:17
作者
Harvey, David [1 ]
van Der Hoeven, Loris [2 ]
机构
[1] Univ New South Wales, Sch Math & Stat, Sydney, NSW 2052, Australia
[2] Ecole Polytech, CNRS, Lab Informat, UMR 7161, F-91128 Palaiseau, France
基金
澳大利亚研究理事会;
关键词
Polynomial multiplication; Finite field; Algorithm; Complexity bound; FFT;
D O I
10.1016/j.jco.2019.03.004
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We prove that for a fixed prime p, polynomials in F-p[X] of degree n may be multiplied in O(n log n4(log)* (n)) bit operations. Previously, the best known bound was O(n log n8(log)* (n)). (C) 2019 Elsevier Inc. All rights reserved.
引用
收藏
页数:18
相关论文
共 22 条
  • [1] ON DISTINGUISHING PRIME-NUMBERS FROM COMPOSITE NUMBERS
    ADLEMAN, LM
    POMERANCE, C
    RUMELY, RS
    [J]. ANNALS OF MATHEMATICS, 1983, 117 (01) : 173 - 206
  • [2] NEW ALGORITHMS FOR DIGITAL CONVOLUTION
    AGARWAL, RC
    COOLEY, JW
    [J]. IEEE TRANSACTIONS ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 1977, 25 (05): : 392 - 410
  • [3] The difference between consecutive primes, II
    Baker, RC
    Harman, G
    Pintz, J
    [J]. PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 2001, 83 : 532 - 562
  • [4] LINEAR FILTERING APPROACH TO COMPUTATION OF DISCRETE FOURIER TRANSFORM
    BLUESTEIN, LI
    [J]. IEEE TRANSACTIONS ON AUDIO AND ELECTROACOUSTICS, 1970, AU18 (04): : 451 - +
  • [5] Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator
    Bostan, Alin
    Gaudry, Pierrick
    Schost, Eric
    [J]. SIAM JOURNAL ON COMPUTING, 2007, 36 (06) : 1777 - 1806
  • [6] ON FAST MULTIPLICATION OF POLYNOMIALS OVER ARBITRARY ALGEBRAS
    CANTOR, DG
    KALTOFEN, E
    [J]. ACTA INFORMATICA, 1991, 28 (07) : 693 - 701
  • [7] diaeresis>urgisser P., 1997, Grundlehren der mathematischen Wissenschaften, V315
  • [8] Faster Integer Multiplication
    Fuerer, Martin
    [J]. STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 57 - 66
  • [9] FASTER INTEGER MULTIPLICATION
    Fuerer, Martin
    [J]. SIAM JOURNAL ON COMPUTING, 2009, 39 (03) : 979 - 1005
  • [10] GOOD IJ, 1958, J ROY STAT SOC B, V20, P361