# Counting points on elliptic curves over finite fields

Journal de théorie des nombres de Bordeaux (1995)

- Volume: 7, Issue: 1, page 219-254
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topSchoof, René. "Counting points on elliptic curves over finite fields." Journal de théorie des nombres de Bordeaux 7.1 (1995): 219-254. <http://eudml.org/doc/247664>.

@article{Schoof1995,

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.},

author = {Schoof, René},

journal = {Journal de théorie des nombres de Bordeaux},

keywords = {elliptic curve over a finite field; reduction algorithm for lattices; torsion points},

language = {eng},

number = {1},

pages = {219-254},

publisher = {Université Bordeaux I},

title = {Counting points on elliptic curves over finite fields},

url = {http://eudml.org/doc/247664},

volume = {7},

year = {1995},

}

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

PB - Université Bordeaux I

VL - 7

IS - 1

SP - 219

EP - 254

AB - 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.

LA - eng

KW - elliptic curve over a finite field; reduction algorithm for lattices; torsion points

UR - http://eudml.org/doc/247664

ER -

## References

top- [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. Zbl0792.11056MR1199989
- [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, Princeton1992.
- [6] Cohen, H.: A course in computational number theory, Graduate Texts in Math. 138, Springer-Verlag, BerlinHeidelbergNew York1993. Zbl0786.11071MR1228206
- [7] Cornacchia, G.: Su di un metodo per la risoluzione in numeri interi dell'equazione Σnh=0 Chxn-hyh = P. Giornale di Mat. di Battaglini46 (1908), 33-90. JFM39.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 Science1994. Zbl0849.14024
- [9] Couveignes, J.-M.: Computing isogenies in low characteristic, Thesis Bordeaux1994. To appear.
- [10] Elkies, N.D.: Explicit Isogenies, manuscript, Boston MA, 1992.
- [11] Hartshorne, R.: Algebraic Geometry, Graduate Texts in Math. 52, Springer-Verlag, BerlinHeidelbergNew York1977. Zbl0367.14001MR463157
- [12] Lang, S.: Elliptic .Functions, Addison-Wesley, Reading MA1973. Zbl0316.14001MR409362
- [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. Zbl0839.11026MR1322712
- [14] Lenstra, H.W.: Elliptic curves and number-theoretical algorithms, Proc. of the International Congress of Math., Berkeley1986, 99-120. Zbl0686.14039MR934218
- [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, Zbl0809.14045MR1153167
- [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, Bordeaux1993.
- [18] Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp.44 (1985), 483-494. Zbl0579.14025MR777280
- [19] Shanks, D.: Class Number, a Theory of Factorization, and Genera, 1969 Number Theory Institute, Proc. of Symp. in Pure Math. 20, AMS, Providence RI1971. Zbl0223.12006MR316385
- [20] Shanks, D.: Five number theoretical algorithms, Proc. 2nd Manitoba conference on numerical math., (Congressus Numerantium VII, Univ. ManitobaWinnipeg), (1972), 51-70. Zbl0307.10015MR371855
- [21] Silverman, J.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, BerlinHeidelbergNew York1986. Zbl0585.14026MR817210

## Citations in EuDML Documents

top- Reynald Lercier, Thomas Sirvent, On Elkies subgroups of $\ell $-torsion points in elliptic curves defined over a finite field
- John E. Cremona, Andrew V. Sutherland, On a theorem of Mestre and Schoof
- François Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques
- Andrew V. Sutherland, A local-global principle for rational isogenies of prime degree
- François Morain, La primalité en temps polynomial
- Lucien Bénéteau, M. Abou Hashish, An alternative way to classify some Generalized Elliptic Curves and their isotopic loops
- François Morain, Computing the cardinality of CM elliptic curves using torsion points
- J. Sijsling, J. Voight, On computing Belyi maps

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.