A LOWER BOUND FOR THE MULTIPLICATION OF POLYNOMIALS MODULO A POLYNOMIAL
Date
1991-06-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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$.
Description
Keywords
Computer Science