Let GF(q) denote the Galois field on q elements, and let n denote a positive integer. Let \(\mu_ q(n)\) be the number of multiplications/divisions required to compute the coefficients of the product of a polynomial of degree \(n-1\) and a polynomial of degree n over GF(q) by means of linear algorithms. Then the authors prove that \[ \mu_ q(n)>\frac{5}{2}n-\frac{n}{4 \log_ qn}-O(\frac{n}{\log^ 2_ qn}). \] The proof is based on some technical lemmas concerned with computing the bilinear forms associated with a set of Hankel matrices by means of quadratic or linear algorithms.