A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields
Michael Kaminski · SIAM Journal on Computing · 2005
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 + \frac{\scriptstyle (q - 1)^2}{\scriptstyle q^5 + (q - 1)^3})n - o(n)$ multiplications.