[Construction effective de l'algorithme asymétrique de multiplication de Chudnovsky dans les corps finis]
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.
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.
Accepté le :
Publié le :
@article{CRMATH_2017__355_7_729_0,
author = {Ballet, St\'ephane and Baudru, Nicolas and Bonnecaze, Alexis and Tukumuli, Mila},
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},
url = {http://www.numdam.org/articles/10.1016/j.crma.2017.06.002/}
}
TY - JOUR AU - Ballet, Stéphane AU - Baudru, Nicolas AU - Bonnecaze, Alexis AU - Tukumuli, Mila 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 UR - http://www.numdam.org/articles/10.1016/j.crma.2017.06.002/ DO - 10.1016/j.crma.2017.06.002 LA - en ID - CRMATH_2017__355_7_729_0 ER -
%0 Journal Article %A Ballet, Stéphane %A Baudru, Nicolas %A Bonnecaze, Alexis %A Tukumuli, Mila %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 %U http://www.numdam.org/articles/10.1016/j.crma.2017.06.002/ %R 10.1016/j.crma.2017.06.002 %G en %F CRMATH_2017__355_7_729_0
Ballet, Stéphane; Baudru, Nicolas; Bonnecaze, Alexis; Tukumuli, Mila. On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation. Comptes Rendus. Mathématique, Tome 355 (2017) no. 7, pp. 729-733. doi : 10.1016/j.crma.2017.06.002. http://www.numdam.org/articles/10.1016/j.crma.2017.06.002/
[1] É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] Curves with many points and multiplication complexity in any extension of , Finite Fields Appl., Volume 5 (1999) no. 4, pp. 364-377
[3] 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] Multiplication algorithm in a finite field and tensor rank of the multiplication, J. Algebra, Volume 272 (2004) no. 1, pp. 173-185
[5] 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] Algebraic complexities and algebraic curves over finite fields, J. Complex., Volume 4 (1988), pp. 285-316
[7] 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] Bilinear complexity of algebras and the Chudnovsky–Chudnovsky interpolation method, J. Complex., Volume 28 (2012), pp. 489-517
[9] Curves with many points and multiplication in finite fields, Proceedings of AGCT-3 Conference, Luminy, France, 17–21 June 1991 (Stichtenoth, H.; Tsfasman, M.A., eds.) (Lect. Notes Math.), Volume vol. 1518, Springer-Verlag, Berlin (1992), pp. 145-169
Cité par Sources :
