A partir de la structure de groupe abélien de l'ensemble des points rationnels d'une courbe elliptique, on améliore un théorème de Shokrollahi concernant l'application de l'algorithme de D.V. Chudnovsky et G.V. Chudnovsky sur des courbes algébriques de genre 1. Plus précisément, on montre que, si , alors la complexité bilinéaire de la multiplication dans des extensions de degré n d'un corps fini est égale à 2n.
In this Note, we improve a result of Shokrollahi who has applied the algorithm of D.V. Chudnovsky and G.V. Chudnovsky to algebraic curves of genus one. More precisely, from the Abelian group structure of the set of rational points on elliptic curves, we show that, if , then the bilinear complexity of the multiplication in all extensions is equal to 2n.
Accepté le :
Publié le :
@article{CRMATH_2006__343_4_265_0,
author = {Chaumine, Jean},
title = {Complexit\'e bilin\'eaire de la multiplication dans des petits corps finis},
journal = {Comptes Rendus. Math\'ematique},
pages = {265--266},
publisher = {Elsevier},
volume = {343},
number = {4},
year = {2006},
doi = {10.1016/j.crma.2006.06.030},
language = {fr},
url = {http://www.numdam.org/articles/10.1016/j.crma.2006.06.030/}
}
TY - JOUR AU - Chaumine, Jean TI - Complexité bilinéaire de la multiplication dans des petits corps finis JO - Comptes Rendus. Mathématique PY - 2006 SP - 265 EP - 266 VL - 343 IS - 4 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2006.06.030/ DO - 10.1016/j.crma.2006.06.030 LA - fr ID - CRMATH_2006__343_4_265_0 ER -
%0 Journal Article %A Chaumine, Jean %T Complexité bilinéaire de la multiplication dans des petits corps finis %J Comptes Rendus. Mathématique %D 2006 %P 265-266 %V 343 %N 4 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2006.06.030/ %R 10.1016/j.crma.2006.06.030 %G fr %F CRMATH_2006__343_4_265_0
Chaumine, Jean. Complexité bilinéaire de la multiplication dans des petits corps finis. Comptes Rendus. Mathématique, Tome 343 (2006) no. 4, pp. 265-266. doi : 10.1016/j.crma.2006.06.030. http://www.numdam.org/articles/10.1016/j.crma.2006.06.030/
[1] Curves with many points and multiplication complexity in any extension of , Finite Fields and Their Applications, Volume 5 (1999), pp. 364-377
[2] J. Chaumine, Corps de Fonctions Algébriques et Algorithme de D.V. Chudnovsky et G.V. Chudnovsky pour la Multiplication dans les Corps Finis, Thèse, Université de la Polynésie française, 2005
[3] Algebraic complexities and algebraic curves over finite fields, Journal of Complexity, Volume 4 (1988), pp. 285-316
[4] Characterization of division algebras of minimal rank and the structure of their algorithm varieties, SIAM J. Comput., Volume 12 (1983) no. 1, pp. 101-117
[5] Optimal algorithms for multiplication in certain finite fields using elliptic curves, SIAM J. Comput., Volume 21 (1992) no. 6, pp. 1193-1198
[6] On the rank of certain finite fields, Comput. Complexity, Volume 1 (1991), pp. 157-181
[7] Curves with many points and multiplication in finite fields, Lecture Notes in Mathematics, vol. 1518, Springer-Verlag, Berlin, 1992, pp. 145-169
[8] The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986
[9] On multiplication in algebraic extension fields, Theoretical Computer Science, Volume 8 (1979), pp. 359-377
Cité par Sources :
