A lower bound for the multiplication of polynomials modulo a polynomial

DOI10.1016/0020-0190(92)90159-SzbMath0766.11050MaRDI QIDQ1197994

Nader H. Bshouty

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitylinear codesmultiplicative complexityquadratic algorithmsmultiplication of two polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06)

Related Items (1)

Gaps between prime numbers and tensor rank of multiplication in finite fields

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\)]
• On the algorithmic complexity of associative algebras
• The computational complexity of a set of quadratic functions
• On the complexity of multiplication in finite fields
• Gaussian elimination is not optimal
• On multiplication of 2 \(\times\) 2 matrices
• Multiplicative complexity of polynomial multiplication over finite fields
• On the Number of Multiplications Required for Matrix Multiplication
• A new approach to error-correcting codes
• Algebraic complexities and algebraic curves over finite fields
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A lower bound for the multiplication of polynomials modulo a polynomial