×
Morain, François

Computing the number of points on an elliptic curve over a finite field: algorithmic aspects. (Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques.) (French) Zbl 0843.11030

J. Théor. Nombres Bordx. 7, No. 1, 255-282 (1995).
The author describes in some detail his implementation of Schoof’s algorithm to compute the number of rational points on an elliptic curve over a prime field. His algorithm depends on the practical improvements of Atkin and Elkies. The author explains how to compute convenient equations of certain modular curves and how to find factors of the division polynomials. He illustrates his efficient program by computing the number of points on an elliptic curve modulo the 500 digit prime \(p= 10^{499}+ 153\).
Reviewer: R.Schoof (Roma)

Cited in 1 Review
Cited in 15 Documents

MSC:

11G20 Curves over finite and local fields
14Q05 Computational aspects of algebraic curves
11F11 Holomorphic modular forms of integral weight
11Y16 Number-theoretic algorithms; complexity

Keywords:

factors of division polynomials; Schoof’s algorithm; number of rational points; elliptic curve; prime field; modular curves
PDF BibTeX XML Cite
\textit{F. Morain}, J. Théor. Nombres Bordx. 7, No. 1, 255--282 (1995; Zbl 0843.11030)
Full Text: DOI Numdam EuDML EMIS
  • logo of hbz
  • logo of WorldCat

References:

[1] Atkin, A.O.L., The number of points on an elliptic curve modulo a prime, Manuscrit, 1988.
[2] Atkin, A.O.L.,, 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, , vol. 476, Springer, 1975, Proceedings International Summer School University of Antwerp, RUCA, July 17-Agust 3, 1972. · Zbl 0315.14014
[4] Charlap, L.S., Coley, R., et Robbins, D.P., Enumeration of rational points on elliptic curves over finite fields, Manuscrit, 1991.
[5] Couveignes, J.-M. et Morain, F., Schoof ’s algorithm and isogeny cycles, ANTS-I (L. Adleman et M.-D. Huang, Réd.), , vol. 877, Springer-Verlag, 1994, p. 43-58. · Zbl 0849.14024
[6] Couveignes, J.-M., Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, juillet 1994.
[7] Deligne, P. et Rapoport, M., Les schémas de modules de courbes elliptiques, Modular functions of one variable II (P. Deligne et W. Kuyk, Réd.), , vol. 349, Springer, 1973, Proceedings International Summer School University of Antwerp, RUCA, July 17-Agust 3, 1972, p. 143-316. · Zbl 0281.14010
[8] Deligne, P. et Serre, J.P., Formes modulaires de poids 1, Ann. scient. Éc. Norm. Sup.7 (1974), 507-530. · Zbl 0321.10026
[9] Dewaghe, L., Remarques sur l’algorithme SEA, en préparation, décembre 1994.
[10] Elkies, Noam D., Explicit isogenies, Manuscrit, 1991.
[11] Fricke, R., Lehrbuch der Algebra, III, F. Vieweg and Sohn, Braunschweig, 1928.
[12] Knuth, D.E., The Art of Computer Programming: Seminumerical algorithms, Addison-Wesley, 1981. · Zbl 0477.65002
[13] Lehmann, F., Maurer, M., Müller, V., et Shoup, V., 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.), , vol. 877, Springer-Verlag, 1994, p. 60-70. · Zbl 0839.11026
[14] Lercier, R. et Morain, F., Counting points on elliptic curves over Fpn using Couveignes’s algorithm, Rapport de Recherche LIX/RR/95/09, École Polytechnique, septembre 1995.
[15] Lercier, R. et Morain, F., 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.), ., no. 921, 1995, p. 79-94. · Zbl 0903.11029
[16] Mahler, K., On a class of non-linear functionat equations connected with modular functions, J. Austral. Math. Soc. Ser. A 22 (1976), 65-120. · Zbl 0345.39002
[17] Mazur, B., Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math.47 (1977), 33-186. · Zbl 0394.14008
[18] Müller, V., Looking for the eigenvalue in Schoof’s algorithm, en préparation, octobre 1994.
[19] Schoeneberg, B., Elliptic modular functions, Die Grundlehren der mathema tischen Wissenschaften in Einzeldarstellungen, vol. 203, Springer-Verlag, 1974. · Zbl 0285.10016
[20] Schoof, R., Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp.44 (1985), 483-494. · Zbl 0579.14025
[21] Schoof, René, Counting points on elliptic curves over finite fields, J. Théorie des Nombres de Bordeaux, 7 (1995), 219-254. · Zbl 0852.11073
[22] Silverman, J.H., The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer,1986. · Zbl 0585.14026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.