A lower bound for the multiplication of polynomials modulo a polynomial
type: Item
instance of: scholarly article
title: A lower bound for the multiplication of polynomials modulo a polynomial
zbMATH Open document ID: 0766.11050
DOI: 10.1016/0020-0190(92)90159-S
author: Nader H. Bshouty
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94B05
zbMATH DE Number: 92071
zbMATH Keywords: computational complexity
zbMATH Keywords: quadratic algorithms
zbMATH Keywords: linear codes
zbMATH Keywords: multiplicative complexity
zbMATH Keywords: multiplication of two polynomials
reviewed by: Giovanni Gallo
MaRDI profile type: Publication
cites work: On the algorithmic complexity of associative algebras
cites work: Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \(G[u]/<Q(u)^{\ell}>\), \(\ell >1\)
cites work: Q3776615
cites work: On the Number of Multiplications Required for Matrix Multiplication
cites work: Algebraic complexities and algebraic curves over finite fields
cites work: Q4162484
cites work: The computational complexity of a set of quadratic functions
cites work: Multiplicative complexity of polynomial multiplication over finite fields
cites work: On the complexity of multiplication in finite fields
cites work: A new approach to error-correcting codes
cites work: Gaussian elimination is not optimal
cites work: Q3946078
cites work: On multiplication of 2 \(\times\) 2 matrices
description: scientific article; zbMATH DE number 92071