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

## 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