On multiplication in algebraic extension fields

DOI10.1016/0304-3975(79)90017-3zbMath0404.12016OpenAlexW2035284794MaRDI QIDQ1256512

Shmuel Winograd

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90017-3

zbMATH Keywords

Algorithm

Mathematics Subject Classification ID

Polynomials in general fields (irreducibility, etc.) (12E05) Polynomials over commutative rings (13B25) Algorithms in computer science (68W99)

Related Items (24)

An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields ⋮ Optimization of the scalar complexity of Chudnovsky\(^2\) multiplication algorithms in finite fields ⋮ Multiplicative complexity of direct sums of quadratic systems ⋮ 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 some bounds for symmetric tensor rank of multiplication in finite fields ⋮ Chudnovsky-type algorithms over the projective line using generalized evaluation maps ⋮ Tower of algebraic function fields with maximal Hasse-Witt invariant and tensor rank of multiplication in any extension of \(\mathbb{F}_2\) and \(\mathbb{F}_3\) ⋮ On the tensor rank of multiplication in any extension of \(\mathbb F_2\) ⋮ Multiplication algorithm in a finite field and tensor rank of the multiplication. ⋮ On the complexity of multiplication in finite fields ⋮ On the tensor rank of the multiplication in the finite fields ⋮ An optimal algorithm for multiplication in \(\mathbb{F}_{256}/\mathbb{F}_ 4\) ⋮ Circuits for computing the GCD of two polynomials over an algebraic number field ⋮ Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \(G[u/\langle{} u^ n \rangle\)] ⋮ On the rank of certain finite fields ⋮ Efficient randomized generation of optimal algorithms for multiplication in certain finite fields ⋮ On the bounds of the bilinear complexity of multiplication in some finite fields ⋮ On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields ⋮ On the bilinear complexity of the multiplication in small finite fields ⋮ Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\) ⋮ On the direct sum conjecture in the straight line model ⋮ On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry ⋮ New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields ⋮ Quasi-optimal algorithms for multiplication in the extensions of \(\mathbb F_{16}\) of degree 13, 14 and 15

Cites Work

• On computing the Discrete Fourier Transform
• Some bilinear forms whose multiplicative complexity depends on the field of constants
• Algebras Having Linear Multiplicative Complexities

This page was built for publication: On multiplication in algebraic extension fields