To evaluate the coefficients of the product of two polynomials of degree n, one may evaluate these polynomials at 2 n + 1 points (such as the ( 2 n + 1 )th roots of 1 ), then pairwise multiply the results and finally obtain the desired coefficients by interpolation. This scheme uses 2 n + 1 bilinear (nonscalar) multiplications, but it does not work over finite fields F _q that have q < n elements. The known upper bound on the number M ( q , n ) of bilinear multiplications is superlinear; this paper establishes a new sharp bound, M ( q , n ) = 3 n + 1 − ⌊ q&slash;2 ⌋, whenever q/2 < n < q + 1, and a new record lower bound, M( q , n ) > 3 n − n/(log _q n − 3 ) for any q greater than 2. As is customary, the authors assume bilinear algorithms and estimate the number of bilinear multiplications. Their proof techniques are novel; they rely on the analysis of linear recurrence sequences and Hankel matrices, while the previous lower bounds on M ( q , n ) were obtained by studying the associated linear codes over F _q, which gave inferior estimates for M( q , n ).

This paper is a theoretical and technical advance. It will primarily interest researchers in the area of the design and analysis of algorithms for computations with polynomials over finite fields.