Counting points on elliptic curves over finite fields
Journal de théorie des nombres de Bordeaux, Tome 7 (1995) no. 1, pp. 219-254.

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.

@article{JTNB_1995__7_1_219_0,
     author = {Schoof, Ren\'e},
     title = {Counting points on elliptic curves over finite fields},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {219--254},
     publisher = {Universit\'e Bordeaux I},
     volume = {7},
     number = {1},
     year = {1995},
     mrnumber = {1413578},
     zbl = {0852.11073},
     language = {en},
     url = {http://archive.numdam.org/item/JTNB_1995__7_1_219_0/}
}
TY  - JOUR
AU  - Schoof, René
TI  - Counting points on elliptic curves over finite fields
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1995
SP  - 219
EP  - 254
VL  - 7
IS  - 1
PB  - Université Bordeaux I
UR  - http://archive.numdam.org/item/JTNB_1995__7_1_219_0/
LA  - en
ID  - JTNB_1995__7_1_219_0
ER  - 
%0 Journal Article
%A Schoof, René
%T Counting points on elliptic curves over finite fields
%J Journal de théorie des nombres de Bordeaux
%D 1995
%P 219-254
%V 7
%N 1
%I Université Bordeaux I
%U http://archive.numdam.org/item/JTNB_1995__7_1_219_0/
%G en
%F JTNB_1995__7_1_219_0
Schoof, René. Counting points on elliptic curves over finite fields. Journal de théorie des nombres de Bordeaux, Tome 7 (1995) no. 1, pp. 219-254. http://archive.numdam.org/item/JTNB_1995__7_1_219_0/

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

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

[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

[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

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

[12] Lang, S.: Elliptic .Functions, Addison-Wesley, Reading MA 1973. | MR | Zbl

[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

[14] Lenstra, H.W.: Elliptic curves and number-theoretical algorithms, Proc. of the International Congress of Math., Berkeley 1986, 99-120. | MR | Zbl

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

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

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

[20] Shanks, D.: Five number theoretical algorithms, Proc. 2nd Manitoba conference on numerical math., (Congressus Numerantium VII, Univ. Manitoba Winnipeg), (1972), 51-70. | MR | Zbl

[21] Silverman, J.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, Berlin Heidelberg New York 1986. | MR | Zbl