Faster polynomial multiplication over finite fields

(with Joris van der Hoeven and Grégoire Lecerf)

J. ACM 63 (2017), no. 6, Article 52 (DOI).

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 Mp(n) denote the bit complexity of multiplying two polynomials in Fp[X] of degree less than n. For n large compared to p, we establish the bound Mp(n) = O(n log n 8log* 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 Mp(n) = O(n log n log log n log p), which essentially goes back to the 1970s.

Preprint version

The following version includes some extra material on a conjectural algorithm that improves the 8 to 4, but this did not make it into the published version.

arXiv preprint (July 2014).

HAL preprint (July 2014).


Back to the main page