Let be a prime, and let denote the bit complexity of multiplying two polynomials in of degree less than . For large compared to , we establish the bound , where is the iterated logarithm. This is the first known Fürer-type complexity bound for , and improves on the previously best known bound .

Authors: David Harvey, Joris van der Hoeven, Grégoire Lecerf

Keywords: Polynomial multiplication, finite field, algorithm, complexity bound, FFT

A.M.S. subject classification: 68W30, 68Q17, 68W40

View: Html, TeXmacs, Pdf, BibTeX