[On the bilinear complexity of the multiplication in small finite fields]
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.
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.
Accepted:
Published online:
Jean Chaumine 1
@article{CRMATH_2006__343_4_265_0, author = {Jean Chaumine}, 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}, }
Jean Chaumine. Complexité bilinéaire de la multiplication dans des petits corps finis. Comptes Rendus. Mathématique, Volume 343 (2006) no. 4, pp. 265-266. doi : 10.1016/j.crma.2006.06.030. https://comptes-rendus.academie-sciences.fr/mathematique/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
Cited by Sources:
Comments - Policy