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

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.

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.

Classification:  11G20,  11F11 
@article{JTNB_1995__7_1_255_0,
     author = {Morain, Fran\c cois},
     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},
     publisher = {Universit\'e Bordeaux I},
     volume = {7},
     number = {1},
     year = {1995},
     pages = {255-282},
     zbl = {0843.11030},
     mrnumber = {1413579},
     language = {fr},
     url = {http://www.numdam.org/item/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, Volume 7 (1995) no. 1, pp. 255-282. http://www.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 376533 | Zbl 0315.14014

[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 1322711 | Zbl 0849.14024

[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 337993 | Zbl 0281.14010

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

[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 633878

[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 1322712 | Zbl 0839.11026

[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 1367512 | Zbl 0903.11029

[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 441867 | Zbl 0345.39002

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

[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 412107 | Zbl 0285.10016

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

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

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