A lower bound for the multiplication of polynomials modulo a polynomial (Q1197994): Difference between revisions

In 1983 \textit{A. Lempel}, \textit{G. Seroussi} and \textit{S. Winograd} [Theor. Comput. Sci. 22, 285-296 (1983; Zbl 0498.68027)] proved the lower bound \((2+1/(q-1))n-o(n)\) for the multiplicative complexity of the multiplication of two polynomials of degree \(n-1\) modulo an irreducible polynomial \(p\) of degree \(n\) over a finite field \(F\) with \(q\) elements. using a combination of the coding method and the substitution method the author generalizes this result to any kind of polynomials.