On the complexity of multiplication in finite fields

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

zbMATH Keywords

bilinear complexitylinear lower boundnth degree extension of a finite fieldpolynomials with indeterminate coefficientsquasi-linear upper bound

Mathematics Subject Classification ID

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