Comptes Rendus
no. 4
Géométrie algébrique
Complexité bilinéaire de la multiplication dans des petits corps finis

Présenté par : Yves Meyer

Jean Chaumine1
1 Département de mathématiques, université de la Polynésie française, B.P. 6570, 98702 Faa'a, Tahiti, Polynésie française
Comptes Rendus. Mathématique, Volume 343 (2006) no. 4, pp. 265-266.

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 12q+1<n⩽12(q+1+ϵ(q)), alors la complexité bilinéaire de la multiplication dans des extensions de degré n d'un corps fini Fq 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 12q+1<n⩽12(q+1+ϵ(q)), then the bilinear complexity of the multiplication in all extensions Fqn is equal to 2n.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2006.06.030
Jean Chaumine 1

1 Département de mathématiques, université de la Polynésie française, B.P. 6570, 98702 Faa'a, Tahiti, Polynésie française 
@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},
}
TY  - JOUR
AU  - Jean Chaumine
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
DO  - 10.1016/j.crma.2006.06.030
LA  - fr
ID  - CRMATH_2006__343_4_265_0
ER  - 
%0 Journal Article
%A Jean Chaumine
%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
%R 10.1016/j.crma.2006.06.030
%G fr
%F CRMATH_2006__343_4_265_0
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] S. Ballet Curves with many points and multiplication complexity in any extension of Fq, 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] D.V. Chudnovsky; G.V. Chudnovsky Algebraic complexities and algebraic curves over finite fields, Journal of Complexity, Volume 4 (1988), pp. 285-316

[4] H.F. De Groote 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] M.A. Shokrollahi Optimal algorithms for multiplication in certain finite fields using elliptic curves, SIAM J. Comput., Volume 21 (1992) no. 6, pp. 1193-1198

[6] M.A. Shokrollahi On the rank of certain finite fields, Comput. Complexity, Volume 1 (1991), pp. 157-181

[7] I.E. Shparlinski; M.A. Tsfasman; S.G. Vlăduţ Curves with many points and multiplication in finite fields, Lecture Notes in Mathematics, vol. 1518, Springer-Verlag, Berlin, 1992, pp. 145-169

[8] J.H. Silverman The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986

[9] S. Winograd On multiplication in algebraic extension fields, Theoretical Computer Science, Volume 8 (1979), pp. 359-377

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Amélioration des bornes de la complexité bilinéaire de la multiplication dans certains corps finis

Stéphane Ballet; Jean Chaumine

C. R. Math (2004)

On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation

Stéphane Ballet; Nicolas Baudru; Alexis Bonnecaze; ...

C. R. Math (2017)

Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm

Kévin Atighehchi; Stéphane Ballet; Alexis Bonnecaze; ...

C. R. Math (2016)