| HomepagePublicationsTalksTeXmacsMathemagix |
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:
Keywords: polynomial multiplication, integer multiplication, algorithm, complexity bound, FFT, finite field