Faster polynomial multiplication over finite fields using cyclotomic coefficient rings

David Harvey; Joris van der Hoeven

doi:10.1016/j.jco.2019.03.004

Faster polynomial multiplication over finite fields using cyclotomic coefficient rings

David Harvey
, Joris van der Hoeven

University of New South Wales

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that for a fixed prime p, polynomials in F_p[X] of degree n may be multiplied in O(nlogn4^{log^∗n}) bit operations. Previously, the best known bound was O(nlogn8^{log^∗n}).

Original language	English
Article number	101404
Journal	Journal of Complexity
Volume	54
DOIs	https://doi.org/10.1016/j.jco.2019.03.004
Publication status	Published - 1 Oct 2019

Keywords

Algorithm
Complexity bound
FFT
Finite field
Polynomial multiplication

Access to Document

10.1016/j.jco.2019.03.004

Cite this

@article{3d0f82bef13b4bfe879ca87c7b8c1b7c,

title = "Faster polynomial multiplication over finite fields using cyclotomic coefficient rings",

abstract = "We prove that for a fixed prime p, polynomials in Fp[X] of degree n may be multiplied in O(nlogn4log∗n) bit operations. Previously, the best known bound was O(nlogn8log∗n).",

keywords = "Algorithm, Complexity bound, FFT, Finite field, Polynomial multiplication",

author = "David Harvey and \{van der Hoeven\}, Joris",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2019",

month = oct,

day = "1",

doi = "10.1016/j.jco.2019.03.004",

language = "English",

volume = "54",

journal = "Journal of Complexity",

issn = "0885-064X",

}

TY - JOUR

T1 - Faster polynomial multiplication over finite fields using cyclotomic coefficient rings

AU - Harvey, David

AU - van der Hoeven, Joris

PY - 2019/10/1

Y1 - 2019/10/1

N2 - We prove that for a fixed prime p, polynomials in Fp[X] of degree n may be multiplied in O(nlogn4log∗n) bit operations. Previously, the best known bound was O(nlogn8log∗n).

AB - We prove that for a fixed prime p, polynomials in Fp[X] of degree n may be multiplied in O(nlogn4log∗n) bit operations. Previously, the best known bound was O(nlogn8log∗n).

KW - Algorithm

KW - Complexity bound

KW - FFT

KW - Finite field

KW - Polynomial multiplication

U2 - 10.1016/j.jco.2019.03.004

DO - 10.1016/j.jco.2019.03.004

M3 - Article

AN - SCOPUS:85063980141

SN - 0885-064X

VL - 54

JO - Journal of Complexity

JF - Journal of Complexity

M1 - 101404

ER -

Faster polynomial multiplication over finite fields using cyclotomic coefficient rings

Abstract

Keywords

Access to Document

Fingerprint

Cite this