Polynomial Multiplication over Finite Fields in Time O(n logn).

Assuming a widely believed hypothesis concerning the least prime in an arithmetic progression, we show that polynomials of degree less than n over a finite field F_q with q elements can be multiplied in time O(n logq log(n logq)), uniformly in q. Under the same hypothesis, we show how to multiply two n-bit integers in time O(n logn); this algorithm is somewhat simpler than the unconditional algorithm from the companion paper [22]. Our results hold in the Turing machine model with a finite number of tapes. [ABSTRACT FROM AUTHOR]