Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45742
Title: A LOWER BOUND FOR THE MULTIPLICATION OF POLYNOMIALS MODULO A POLYNOMIAL
Authors: Bshouty, Nader H.
Keywords: Computer Science
Issue Date: 1-Jun-1991
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$.
URI: http://hdl.handle.net/1880/45742
Appears in Collections:Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1991-433-17.pdf790.4 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.