Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques
Journal de théorie des nombres de Bordeaux, Tome 7 (1995) no. 1, pp. 255-282.

Nous décrivons dans cet article les algorithmes nécessaires à une implantation efficace de la méthode de Schoof pour le calcul du nombre de points sur une courbe elliptique dans un corps fini. Nous tentons d’unifier pour cela les idées d’Atkin et d’Elkies. En particulier, nous décrivons le calcul d’équations pour X 0 (ℓ), ℓ premier, ainsi que le calcul efficace de facteurs des polynômes de division d’une courbe elliptique.

We describe the algorithms that are needed for an efficient implementation of Schoof’s method for computing the number of points on en elliptic curve over a finite field. We try to unify the ideas of Atkin and Elkies. In particular, we describe the computation of equations for X 0 (ℓ),ℓ a prime number, as well as the efficient computation of factors of the division polynomials of an elliptic curve.

Classification : 11G20, 11F11
Mots-clés : courbes elliptiques, corps finis, algorithme de Schoof, formes modulaires, équations modulaires, polynômes de division 
@article{JTNB_1995__7_1_255_0,
     author = {Morain, Fran\c{c}ois},
     title = {Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {255--282},
     publisher = {Universit\'e Bordeaux I},
     volume = {7},
     number = {1},
     year = {1995},
     mrnumber = {1413579},
     zbl = {0843.11030},
     language = {fr},
     url = {http://archive.numdam.org/item/JTNB_1995__7_1_255_0/}
}
TY  - JOUR
AU  - Morain, François
TI  - Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1995
SP  - 255
EP  - 282
VL  - 7
IS  - 1
PB  - Université Bordeaux I
UR  - http://archive.numdam.org/item/JTNB_1995__7_1_255_0/
LA  - fr
ID  - JTNB_1995__7_1_255_0
ER  - 
%0 Journal Article
%A Morain, François
%T Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques
%J Journal de théorie des nombres de Bordeaux
%D 1995
%P 255-282
%V 7
%N 1
%I Université Bordeaux I
%U http://archive.numdam.org/item/JTNB_1995__7_1_255_0/
%G fr
%F JTNB_1995__7_1_255_0
Morain, François. Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques. Journal de théorie des nombres de Bordeaux, Tome 7 (1995) no. 1, pp. 255-282. http://archive.numdam.org/item/JTNB_1995__7_1_255_0/

[1] A.O.L. Atkin, The number of points on an elliptic curve modulo a prime, Manuscrit, 1988.

[2] A.O.L. Atkin,, The number of points on an elliptic curve modulo a prime (ii), Manuscrit, 1992.

[3] B. J. Birch et W. Kuyk (Réd.), Modular functions of one variable IV, Lecture Notes in Math., vol. 476, Springer, 1975, Proceedings International Summer School University of Antwerp, RUCA, July 17-Agust 3, 1972. | MR | Zbl

[4] L.S. Charlap, R. Coley, et D.P. Robbins, Enumeration of rational points on elliptic curves over finite fields, Manuscrit, 1991.

[5] J.-M. Couveignes et F. Morain, Schoof 's algorithm and isogeny cycles, ANTS-I (L. Adleman et M.-D. Huang, Réd.), Lecture Notes in Comput. Sci., vol. 877, Springer-Verlag, 1994, p. 43-58. | MR | Zbl

[6] J.-M. Couveignes, Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, juillet 1994.

[7] P. Deligne et M. Rapoport, Les schémas de modules de courbes elliptiques, Modular functions of one variable II (P. Deligne et W. Kuyk, Réd.), Lecture Notes in Math., vol. 349, Springer, 1973, Proceedings International Summer School University of Antwerp, RUCA, July 17-Agust 3, 1972, p. 143-316. | MR | Zbl

[8] P. Deligne et J.P., Serre, Formes modulaires de poids 1, Ann. scient. Éc. Norm. Sup. 7 (1974), 507-530. | Numdam | MR | Zbl

[9] L. Dewaghe, Remarques sur l'algorithme SEA, en préparation, décembre 1994.

[10] Noam D. Elkies, Explicit isogenies, Manuscrit, 1991.

[11] R. Fricke, Lehrbuch der Algebra, III, F. Vieweg and Sohn, Braunschweig, 1928.

[12] D.E. Knuth, The Art of Computer Programming: Seminumerical algorithms, Addison-Wesley, 1981. | MR

[13] F. Lehmann, M. Maurer, V. Müller, et V. Shoup, Counting the number of points on elliptic curves over finite fields of characteristic greater than three, ANTS-I (L. Adleman et M.-D. Huang, Réd.), Lecture Notes in Comput. Sci., vol. 877, Springer-Verlag, 1994, p. 60-70. | MR | Zbl

[14] R. Lercier et F. Morain, Counting points on elliptic curves over Fpn using Couveignes's algorithm, Rapport de Recherche LIX/RR/95/09, École Polytechnique, septembre 1995.

[15] R. Lercier et F. Morain, Counting the number of points on elliptic curves over finite fields: strategies and performances, Advances in Cryptology- EUROCRYPT'95 (L. C. GUILLOU et J.-J. QUISQUATER, réd.), Lecture Notes in Comput. Sci., no. 921, 1995, p. 79-94. | MR | Zbl

[16] K. Mahler, On a class of non-linear functionat equations connected with modular functions, J. Austral. Math. Soc. Ser. A 22 (1976), 65-120. | MR | Zbl

[17] B. Mazur, Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 33-186. | Numdam | MR | Zbl

[18] V. Müller, Looking for the eigenvalue in Schoof's algorithm, en préparation, octobre 1994.

[19] B. Schoeneberg, Elliptic modular functions, Die Grundlehren der mathema tischen Wissenschaften in Einzeldarstellungen, vol. 203, Springer-Verlag, 1974. | MR | Zbl

[20] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483-494. | MR | Zbl

[21] René Schoof, Counting points on elliptic curves over finite fields, J. Théorie des Nombres de Bordeaux, 7 (1995), 219-254. | Numdam | MR | Zbl

[22] J.H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer,1986. | MR | Zbl