Search the site

Table of contents for this issue | Previous article | Next article
René Schoof
Counting points on elliptic curves over finite fields
Journal de théorie des nombres de Bordeaux, 7 no. 1 (1995), p. 219-254, doi: 10.5802/jtnb.142
Article PDF | Reviews MR 1413578 | Zbl 0852.11073 | 6 citations in Cedram

Résumé - Abstract

We describe three algorithms to count the number of points on an elliptic curve over a finite field. The first one is very practical when the finite field is not too large ; it is based on Shanks’s baby-step-giant-step strategy. The second algorithm is very efficient when the endomorphism ring of the curve is known. It exploits the natural lattice structure of this ring. The third algorithm is based on calculations with the torsion points of the elliptic curve [18]. This deterministic polynomial time algorithm was impractical in its original form. We discuss several practical improvements by Atkin and Elkies.


[1] Atkin, A.O.L.: The Number of Points an an Elliptic Curve Modulo a Prime, manuscript, Chicago IL, January 1, 1988.
[2] Atkin, A.O.L.: Several public email messages, 1990-1992.
[3] Atkin, A.O.L. and Morain, F.: Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-67.  MR 1199989 |  Zbl 0792.11056
[4] Batut, C., Bernardi, D., Cohen, H. and Olivier, M.: User's Guide to PARI-GP, version 1.30, Bordeaux February 1, 1990.
[5] Charlap, L.S., Coley, R. and Robbins, D.P.: Enumeration of rational Points on Elliptic Curves over Finite Fields, manuscript, Princeton 1992.
[6] Cohen, H.: A course in computational number theory, Graduate Texts in Math. 138, Springer-Verlag, Berlin Heidelberg New York 1993.  MR 1228206 |  Zbl 0786.11071
[7] Cornacchia, G.: Su di un metodo per la risoluzione in numeri interi dell'equazione Σnh=0 Chxn-hyh = P. Giornale di Mat. di Battaglini 46 (1908), 33-90.  JFM 39.0258.02
[8] Couveignes, J.-M. and Morain, F.: Schoof's algorithm and isogeny cycles, Proceedings of the ANTS conference, Ithaca 1994, Lecture Notes in Computer Science 1994.  Zbl 0849.14024
[9] Couveignes, J.-M.: Computing isogenies in low characteristic, Thesis Bordeaux 1994. To appear.
[10] Elkies, N.D.: Explicit Isogenies, manuscript, Boston MA, 1992.
[11] Hartshorne, R.: Algebraic Geometry, Graduate Texts in Math. 52, Springer-Verlag, Berlin Heidelberg New York 1977.  MR 463157 |  Zbl 0367.14001
[12] Lang, S.: Elliptic .Functions, Addison-Wesley, Reading MA 1973.  MR 409362 |  Zbl 0316.14001
[13] Lehmann, F., Maurer, M., Müller, V. and Shoup, V.: Counting the number of points on elliptic curves over finite fields of characteristic greater than three. Preprint 1994.  MR 1322712
[14] Lenstra, H.W.: Elliptic curves and number-theoretical algorithms, Proc. of the International Congress of Math., Berkeley 1986, 99-120.  MR 934218 |  Zbl 0686.14039
[15] Lenstra, H.W.: Letter to H. Cohen, August 16, 1990.
[16] Menezes, A.J., Vanstone, S.A. and Zuccherato, R.J.: Counting points on elliptic curves over F2m, Math. Comp. 60 (1993), 407-420,  MR 1153167 |  Zbl 0809.14045
[17] Morain, F.: Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, Proceedings of the Journées Arithmétiques, Bordeaux 1993.
[18] Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483-494.  MR 777280 |  Zbl 0579.14025
[19] Shanks, D.: Class Number, a Theory of Factorization, and Genera, 1969 Number Theory Institute, Proc. of Symp. in Pure Math. 20, AMS, Providence RI 1971.  MR 316385 |  Zbl 0223.12006
[20] Shanks, D.: Five number theoretical algorithms, Proc. 2nd Manitoba conference on numerical math., (Congressus Numerantium VII, Univ. Manitoba Winnipeg), (1972), 51-70.  MR 371855 |  Zbl 0307.10015
[21] Silverman, J.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, Berlin Heidelberg New York 1986.  MR 817210 |  Zbl 0585.14026