Comptes Rendus
Number theory/Computer science
On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation
Comptes Rendus. Mathématique, Volume 355 (2017) no. 7, pp. 729-733.

The Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity uniformly linear with respect to the degree of the extension. Recently, Randriambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. In this note, we describe the construction of this asymmetric method without derived evaluation. To do this, we translate this generalization into the language of algebraic function fields and we give a strategy of construction and implementation.

L'algorithme de multiplication dans les corps finis de Chudnovsky a une complexité bilinéaire uniformément linéaire en le degré de l'extension. Randriambololona a récemment généralisé cette méthode en introduisant l'asymétrie dans la procédure d'interpolation et en obtenant ainsi de nouvelles bornes sur la complexité bilinéaire. Dans cette note, nous décrivons la construction de cette méthode asymétrique sans évaluation dérivée. Pour ce faire, nous traduisons cette généralisation dans le langage des corps de fonctions algébriques, et nous donnons une stratégie de construction et d'implantation.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2017.06.002

Stéphane Ballet 1; Nicolas Baudru 2; Alexis Bonnecaze 1; Mila Tukumuli 1

1 Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
2 Aix Marseille Univ, CNRS, Centrale Marseille, LIF, Marseille, France
@article{CRMATH_2017__355_7_729_0,
     author = {St\'ephane Ballet and Nicolas Baudru and Alexis Bonnecaze and Mila Tukumuli},
     title = {On the construction of the asymmetric {Chudnovsky} multiplication algorithm in finite fields without derivated evaluation},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {729--733},
     publisher = {Elsevier},
     volume = {355},
     number = {7},
     year = {2017},
     doi = {10.1016/j.crma.2017.06.002},
     language = {en},
}
TY  - JOUR
AU  - Stéphane Ballet
AU  - Nicolas Baudru
AU  - Alexis Bonnecaze
AU  - Mila Tukumuli
TI  - On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation
JO  - Comptes Rendus. Mathématique
PY  - 2017
SP  - 729
EP  - 733
VL  - 355
IS  - 7
PB  - Elsevier
DO  - 10.1016/j.crma.2017.06.002
LA  - en
ID  - CRMATH_2017__355_7_729_0
ER  - 
%0 Journal Article
%A Stéphane Ballet
%A Nicolas Baudru
%A Alexis Bonnecaze
%A Mila Tukumuli
%T On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation
%J Comptes Rendus. Mathématique
%D 2017
%P 729-733
%V 355
%N 7
%I Elsevier
%R 10.1016/j.crma.2017.06.002
%G en
%F CRMATH_2017__355_7_729_0
Stéphane Ballet; Nicolas Baudru; Alexis Bonnecaze; Mila Tukumuli. On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation. Comptes Rendus. Mathématique, Volume 355 (2017) no. 7, pp. 729-733. doi : 10.1016/j.crma.2017.06.002. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2017.06.002/

[1] N. Arnaud Évaluation dérivées, multiplication dans les corps finis et codes correcteurs, Université de la Méditerranée, Institut de mathématiques de Luminy, France, 2006 (PhD Thesis)

[2] S. Ballet Curves with many points and multiplication complexity in any extension of Fq, Finite Fields Appl., Volume 5 (1999) no. 4, pp. 364-377

[3] S. Ballet; A. Bonnecaze; M. Tukumuli On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields, J. Algebra Appl., Volume 15 (2016) no. 1

[4] S. Ballet; R. Rolland Multiplication algorithm in a finite field and tensor rank of the multiplication, J. Algebra, Volume 272 (2004) no. 1, pp. 173-185

[5] S. Ballet; R. Rolland On the bilinear complexity of the multiplication in finite fields, Proceedings of the Conference Arithmetic, Geometry and Coding Theory (AGCT 2003), Semin. Congr., vol. 11, Société mathématique de France, 2005, pp. 179-188

[6] D.V. Chudnovsky; G.V. Chudnovsky Algebraic complexities and algebraic curves over finite fields, J. Complex., Volume 4 (1988), pp. 285-316

[7] J. Pieltant; H. Randriambololona New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields, Math. Comput., Volume 84 (2015), pp. 2023-2045

[8] H. Randriambololona Bilinear complexity of algebras and the Chudnovsky–Chudnovsky interpolation method, J. Complex., Volume 28 (2012), pp. 489-517

[9] I. Shparlinski; M. Tsfasman; S. Vladut Curves with many points and multiplication in finite fields, Proceedings of AGCT-3 Conference, Luminy, France, 17–21 June 1991 (H. Stichtenoth; M.A. Tsfasman, eds.) (Lect. Notes Math.), Volume vol. 1518, Springer-Verlag, Berlin (1992), pp. 145-169

Cited by Sources:

Comments - Policy