Comptes Rendus
Géométrie algébrique
Complexité bilinéaire de la multiplication dans des petits corps finis
[On the bilinear complexity of the multiplication in small finite fields]
Comptes Rendus. Mathématique, Volume 343 (2006) no. 4, pp. 265-266.

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<n12(q+1+ϵ(q)), then the bilinear complexity of the multiplication in all extensions Fqn 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 12q+1<n12(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.

Received:
Accepted:
Published online:
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

Cited by Sources:

Comments - Policy


Articles of potential interest

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)