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 in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(nlog n8^log∗ n log p), where log∗ n = min{k ∈ ℕ: log ^κ×. log n ≥ 1} stands for the iterated logarithm. This improves on the previously best known bound Mp(n) = O(nlog nlog log nlog p), which essentially goes back to the 1970s.