A lower bound on the complexity of polynomial multiplication over finite fields
It is shown that computing the coefficients of the product of two degree-n polynomials over a q-element field by means of a quadratic algorithm requires at least (3 + (q-1)(2)/ q(5)+( q- 1)(3)) n - o( n) multiplications.
polynomial multiplication quadratic algorithms linear recurring sequences hankel matrices error-correcting codes