A LOWER BOUND FOR THE MULTIPLICATION OF POLYNOMIALS MODULO A POLYNOMIAL

Abstract

In Theoretical Computer Science (1983), Lempel, Seroussi and Winograd proved the lower bound left ( 2~+~1 over {q~-~1} right )~n~-~o(n) for the multiplicative complexity of the multiplication of two polynomials of degree n − 1 modulo an \fBirreducible\fR polynomial p of degree n over a finite field F with q elements. In this paper we prove this lower bound holds for Bany polynomial p of degree n.