On the complexity of multiplication in finite fields
From MaRDI portal
Publication:1171378
DOI10.1016/0304-3975(83)90108-1zbMath0498.68027OpenAlexW2059732659MaRDI QIDQ1171378
Abraham Lempel, Gadiel Seroussi, Shmuel Winograd
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(83)90108-1
bilinear complexitylinear lower boundnth degree extension of a finite fieldpolynomials with indeterminate coefficientsquasi-linear upper bound
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
Related Items
Inversion of two level circulant matrices over \(\mathbb{Z}_{p}\), A lower bound for polynomial multiplication, Multiplicative complexity of direct sums of quadratic systems, Multiplicative complexity of vector valued Boolean functions, On arithmetical algorithms over finite fields, Gaps between prime numbers and tensor rank of multiplication in finite fields, Inversion of circulant matrices over $\mathbf{Z}_m$, On fast multiplication of polynomials over arbitrary algebras, A lower bound for the multiplication of polynomials modulo a polynomial, A survey of some recent bit-parallel \(\mathrm{GF}(2^n)\) multipliers, Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\), Multiplicative complexity of bilinear algorithms for cyclic convolution over finite fields, On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
Cites Work
- Unnamed Item
- Unnamed Item
- On multiplication in algebraic extension fields
- A new approach to error-correcting codes
- Some bilinear forms whose multiplicative complexity depends on the field of constants
- Algebras Having Linear Multiplicative Complexities
- On the number of multiplications necessary to compute certain functions
