Bshouty, Nader H.2008-02-272008-02-271991-06-01http://hdl.handle.net/1880/45742In 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$.EngComputer Scienceunknown1991-433-1710.11575/PRISM/30472