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 complexity; linear codes; multiplicative complexity; quadratic algorithms; multiplication of two polynomials

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94B05: Linear codes (general theory)

11Y16: Number-theoretic algorithms; complexity

11T06: Polynomials over finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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