On the tensor rank of multiplication in any extension of F₂

DOI10.1016/J.JCO.2011.01.008MaRDI QIDQ2431340zbMATH OpenOpenAlexFDO

Authors S. Ballet, Julia Pieltant

Publication date 13 April 2011

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.1864

zbMATH Keywords

algebraic function fieldsalgorithmfinite fieldsGarcia-Stichtenoth towertensor ranktower of function fields

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Vector and tensor algebra, theory of invariants (15A72)

Abstract: In this paper, we obtain new bounds for the tensor rank of multiplication in any extension of $F_2$. In particular, it also enables us to obtain the best known asymptotic bound. In this aim, we use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over $F_2$ of a Garcia-Stichtenoth tower of algebraic function fields defined over $F_{2^4}$.

Review text

The authors obtain new bounds for the tensor rank of multiplication in any extension of \({\mathbb F}_2\). As a particular consequence, they also obtain the best known asymptotic bound. For this purpose, they use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over \({\mathbb F}_2\) of a Garcia-Stichtenoth tower of algebraic function fields defined over \({\mathbb F}_2^4\).

Recommendations

• A note on the tensor rank of the multiplication in certain finite fields
• On the tensor rank of the multiplication in the finite fields
• New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields
• Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of F_q
• 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\)

Cites work

• A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
• Algebraic complexities and algebraic curves over finite fields
• Algebraic function fields and codes
• Algebraic geometry in coding theory and cryptography
• An optimal algorithm for multiplication in \(\mathbb{F}_{256}/\mathbb{F}_ 4\)
• Characterization of Division Algebras of Minimal Rank and the Structure of their Algorithm Varieties
• Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)
• Families of curves over any finite field attaining the generalized Drinfeld-Vladut bound
• scientific article; zbMATH DE number 5896947 (Why is no real title available?)
• scientific article; zbMATH DE number 125907 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• Improved Polynomial Multiplication Formulas over $IF₂$ Using Chinese Remainder Theorem
• KANT V4
• Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of F_q
• Multiplication algorithm in a finite field and tensor rank of the multiplication.
• On multiplication in algebraic extension fields
• On the bounds of the bilinear complexity of multiplication in some finite fields
• On the existence of dimension zero divisors in algebraic function fields defined over F_q
• On the existence of non-special divisors of degree \(g\) and \(g-1\) in algebraic function fields over \(\mathbb{F}_2\)
• On the tensor rank of the multiplication in the finite fields
• Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves

Cited in

(16)

• 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\)
• Construction of asymmetric Chudnovsky-type algorithms for multiplication in finite fields
• The tensor rank of semifields of order 16 and 81
• On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields
• A note on the tensor rank of the multiplication in certain finite fields
• Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
• scientific article; zbMATH DE number 1973908 (Why is no real title available?)
• On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
• Determining the Rank of Tensors in $$\mathbb {F}_q^2\otimes \mathbb {F}_q^3\otimes \mathbb {F}_q^3$$
• Tensor representation of rank-metric codes
• New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields
• Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm
• On some bounds for symmetric tensor rank of multiplication in finite fields
• Chudnovsky-type algorithms over the projective line using generalized evaluation maps
• Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity
• On the rank of certain finite fields

Describes a project that uses

Uses Software

• KANT/KASH

This page was built for publication: On the tensor rank of multiplication in any extension of \(\mathbb F_2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431340)