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.
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.
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}, zbl = {0843.11030}, mrnumber = {1413579}, 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 DA - 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/ UR - https://zbmath.org/?q=an%3A0843.11030 UR - https://www.ams.org/mathscinet-getitem?mr=1413579 LA - fr ID - JTNB_1995__7_1_255_0 ER -
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] 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 376533 | Zbl 0315.14014
[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 1322711 | Zbl 0849.14024
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 337993 | Zbl 0281.14010
et ,[8] Formes modulaires de poids 1, Ann. scient. Éc. Norm. Sup. 7 (1974), 507-530. | Numdam | MR 379379 | Zbl 0321.10026
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 633878
,[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 1322712 | Zbl 0839.11026
, , , 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 1367512 | Zbl 0903.11029
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 441867 | Zbl 0345.39002
,[17] Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 33-186. | Numdam | MR 488287 | Zbl 0394.14008
,[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 412107 | Zbl 0285.10016
,[20] 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] 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] The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer,1986. | MR 817210 | Zbl 0585.14026
,