A lower bound for the multiplication of polynomials modulo a polynomial
From MaRDI portal
Publication:1197994
DOI10.1016/0020-0190(92)90159-SzbMath0766.11050MaRDI QIDQ1197994
Publication date: 16 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
computational complexity; linear codes; multiplicative complexity; quadratic algorithms; multiplication of two polynomials
68Q25: Analysis of algorithms and problem complexity
94B05: Linear codes (general theory)
11Y16: Number-theoretic algorithms; complexity
11T06: Polynomials over finite fields
Related Items
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