Faster Polynomial Multiplication over Finite Fields

Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let p be a prime, and let M p ( n ) denote the bit complexity of multiplying two polynomials...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2017-02, Vol.63 (6), p.1-23
Main Authors: Harvey, David, Hoeven, Joris Van Der, Lecerf, Grégoire
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Complexity
Computer Science
Cryptography
Error correcting codes
Logarithms
Mathematical analysis
Mathematical Software
Polynomials
Stands
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let p be a prime, and let M p ( n ) denote the bit complexity of multiplying two polynomials in F p [ X ] of degree less than n . For n large compared to p , we establish the bound M p ( n ) = O ( n log n 8 log* n log p ), where log * n = min{ k ϵ N: log … k × … log n ≤ 1} stands for the iterated logarithm. This improves on the previously best known bound M p ( n ) = O ( n log n log log n log p ), which essentially goes back to the 1970s.
ISSN:0004-5411
1557-735X
DOI:10.1145/3005344