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$.