A lower bound for the multiplication of polynomials modulo a polynomial (Q1197994): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q1853870 |
Changed an Item |
||
| Property / reviewed by | |||
| Property / reviewed by: Giovanni Gallo / rank | |||
Normal rank | |||
Revision as of 11:31, 29 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A lower bound for the multiplication of polynomials modulo a polynomial |
scientific article |
Statements
A lower bound for the multiplication of polynomials modulo a polynomial (English)
0 references
16 January 1993
0 references
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.
0 references
computational complexity
0 references
quadratic algorithms
0 references
linear codes
0 references
multiplicative complexity
0 references
multiplication of two polynomials
0 references
