Skip to Main content Skip to Navigation
Journal articles

Faster polynomial multiplication over finite fields using cyclotomic coefficient rings

Abstract : We prove that for a fixed prime p, polynomials in F p [X] of degree n may be multiplied in O(n log n 4 log * n) bit operations. Previously, the best known bound was O(n log n 8 log * n).
Document type :
Journal articles
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02350390
Contributor : Joris van der Hoeven <>
Submitted on : Monday, November 23, 2020 - 11:51:01 AM
Last modification on : Saturday, November 28, 2020 - 6:38:54 PM

File

cyclomult.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

David Harvey, Joris van der Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Journal of Complexity, Elsevier, 2019, 54, pp.101404. ⟨10.1016/j.jco.2019.03.004⟩. ⟨hal-02350390⟩

Share

Metrics

Record views

92

Files downloads

98