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 -
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] The Number of Points an an Elliptic Curve Modulo a Prime, manuscript, Chicago IL, January 1, 1988.
:[2] Several public email messages, 1990-1992.
:[3] Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-67. | MR | Zbl
and :[4] User's Guide to PARI-GP, version 1.30, Bordeaux February 1, 1990.
, , and :[5] Enumeration of rational Points on Elliptic Curves over Finite Fields, manuscript, Princeton 1992.
, and :[6] A course in computational number theory, Graduate Texts in Math. 138, Springer-Verlag, Berlin Heidelberg New York 1993. | MR | Zbl
:[7] 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] Schoof's algorithm and isogeny cycles, Proceedings of the ANTS conference, Ithaca 1994, Lecture Notes in Computer Science 1994. | Zbl
and :[9] Computing isogenies in low characteristic, Thesis Bordeaux 1994. To appear.
:[10] Explicit Isogenies, manuscript, Boston MA, 1992.
:[11] Algebraic Geometry, Graduate Texts in Math. 52, Springer-Verlag, Berlin Heidelberg New York 1977. | MR | Zbl
:[12] Elliptic .Functions, Addison-Wesley, Reading MA 1973. | MR | Zbl
:[13] Counting the number of points on elliptic curves over finite fields of characteristic greater than three. Preprint 1994. | MR
, , and :[14] Elliptic curves and number-theoretical algorithms, Proc. of the International Congress of Math., Berkeley 1986, 99-120. | MR | Zbl
:[15] Letter to H. Cohen, August 16, 1990.
:[16] Counting points on elliptic curves over F2m, Math. Comp. 60 (1993), 407-420, | MR | Zbl
, and :[17] 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] Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483-494. | MR | Zbl
:[19] 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] Five number theoretical algorithms, Proc. 2nd Manitoba conference on numerical math., (Congressus Numerantium VII, Univ. Manitoba Winnipeg), (1972), 51-70. | MR | Zbl
:[21] The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, Berlin Heidelberg New York 1986. | MR | Zbl
: