Polynomial multiplication over finite fields in time O(nlogn)


Assuming a widely-believed hypothesis concerning the least prime in an arithmetic progression, we show that two -bit integers can be multiplied in time on a Turing machine with a finite number of tapes; we also show that polynomials of degree less than over a finite field with elements can be multiplied in time , uniformly in .

Authors: David Harvey, Joris van der Hoeven

Keywords: polynomial multiplication, integer multiplication, algorithm, complexity bound, FFT, finite field

View: Html, TeXmacs, Pdf, BibTeX