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 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 , premier, ainsi que le calcul efficace de facteurs des polynômes de division d’une courbe elliptique.
Keywords: 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, Volume 7 (1995) no. 1, pp. 255-282. http://archive.numdam.org/item/JTNB_1995__7_1_255_0/
[1] The number of points on an elliptic curve modulo a prime, Manuscrit, 1988.
,[2] 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] Enumeration of rational points on elliptic curves over finite fields, Manuscrit, 1991.
, , et ,[5] 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
et ,[6] Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, juillet 1994.
,[7] 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
et ,[8] Formes modulaires de poids 1, Ann. scient. Éc. Norm. Sup. 7 (1974), 507-530. | Numdam | MR | Zbl
et ,[9] Remarques sur l'algorithme SEA, en préparation, décembre 1994.
,[10] Explicit isogenies, Manuscrit, 1991.
,[11] Lehrbuch der Algebra, III, F. Vieweg and Sohn, Braunschweig, 1928.
,[12] The Art of Computer Programming: Seminumerical algorithms, Addison-Wesley, 1981. | MR
,[13] 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
, , , et ,[14] Counting points on elliptic curves over Fpn using Couveignes's algorithm, Rapport de Recherche LIX/RR/95/09, École Polytechnique, septembre 1995.
et ,[15] 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
et ,[16] 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] Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 33-186. | Numdam | MR | Zbl
,[18] Looking for the eigenvalue in Schoof's algorithm, en préparation, octobre 1994.
,[19] Elliptic modular functions, Die Grundlehren der mathema tischen Wissenschaften in Einzeldarstellungen, vol. 203, Springer-Verlag, 1974. | MR | Zbl
,[20] Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483-494. | MR | Zbl
,[21] Counting points on elliptic curves over finite fields, J. Théorie des Nombres de Bordeaux, 7 (1995), 219-254. | Numdam | MR | Zbl
,[22] The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer,1986. | MR | Zbl
,