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 ( 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.