Multiplicative complexity of polynomial multiplication over finite fields
Michael Kaminski, Nader H. Bshouty · Journal of the ACM · 1989
Let M q ( n ) denote the number of multiplications required to compute the coefficients of the product of two polynomials of degree n over a q -element field by means of bilinear algorithms. It is shown that M q ( n ) ≱ 3 n - o ( n ). In particular, if q /2 < n ⪇ q + 1, we establish the tight bound M q ( n ) = 3 n + 1 [ q /2].The technique we use can be applied to analysis of algorithms for multiplication of polynomials modulo a polynomial as well.