Faster Polynomial Multiplication over Finite Fields

Abstract

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.