On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields

DOI10.1142/S0219498816500055zbMath1371.11158arXiv1303.7082OpenAlexW1975671803MaRDI QIDQ2788750

Mila Tukumuli, Stéphane Ballet, Alexis Bonnecaze

Publication date: 22 February 2016

Published in: Journal of Algebra and Its Applications (Search for Journal in Brave)

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

zbMATH Keywords

finite fieldmultiplication algorithmbilinear complexityelliptic function fieldinterpolation on algebraic curve

Mathematics Subject Classification ID

Arithmetic theory of algebraic function fields (11R58) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Elliptic curves (14H52) Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30)

Related Items (8)

A strategy to optimize the complexity of Chudnovsky-type algorithms over the projective line ⋮ Finding Optimal Chudnovsky-Chudnovsky Multiplication Algorithms ⋮ Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity ⋮ On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation ⋮ On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry ⋮ Construction of asymmetric Chudnovsky-type algorithms for multiplication in finite fields ⋮ On the arithmetic operations over finite fields of characteristic three with low complexity ⋮ Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm

Cites Work

• Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
• Algebraic function fields and codes
• On the existence of non-special divisors of degree \(g\) and \(g-1\) in algebraic function fields over \(\mathbb{F}_2\)
• An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields
• On the tensor rank of the multiplication in the finite fields
• On multiplication in finite fields
• An optimal algorithm for multiplication in \(\mathbb{F}_{256}/\mathbb{F}_ 4\)
• On multiplication in algebraic extension fields
• The Magma algebra system. I: The user language
• Multiplication algorithm in a finite field and tensor rank of the multiplication.
• Quasi-optimal algorithms for multiplication in the extensions of \(\mathbb F_{16}\) of degree 13, 14 and 15
• On the bounds of the bilinear complexity of multiplication in some finite fields
• Curves with many points and multiplication complexity in any extension of \(\mathbb{F}_q\)
• On the tensor rank of multiplication in any extension of \(\mathbb F_2\)
• Elliptic periods for finite fields
• How to Hash into Elliptic Curves
• Five, six, and seven-term Karatsuba-like formulae
• Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves
• Improved Polynomial Multiplication Formulas over $IF₂$ Using Chinese Remainder Theorem
• Asymptotic Bound for Multiplication Complexity in the Extensions of Small Finite Fields
• Algebraic complexities and algebraic curves over finite fields

This page was built for publication: On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields