Counting points on elliptic curves over finite fields

René Schoof

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

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

Abstract

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

How to cite

top

Schoof, 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. [1] Atkin, A.O.L.: The Number of Points an an Elliptic Curve Modulo a Prime, manuscript, Chicago IL, January 1, 1988. 
  2. [2] Atkin, A.O.L.: Several public email messages, 1990-1992. 
  3. [3] Atkin, A.O.L. and Morain, F.: Elliptic curves and primality proving, Math. Comp.61 (1993), 29-67. Zbl0792.11056MR1199989
  4. [4] Batut, C., Bernardi, D., Cohen, H. and Olivier, M.: User's Guide to PARI-GP, version 1.30, Bordeaux February 1, 1990. 
  5. [5] Charlap, L.S., Coley, R. and Robbins, D.P.: Enumeration of rational Points on Elliptic Curves over Finite Fields, manuscript, Princeton1992. 
  6. [6] Cohen, H.: A course in computational number theory, Graduate Texts in Math. 138, Springer-Verlag, BerlinHeidelbergNew York1993. Zbl0786.11071MR1228206
  7. [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. [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. [9] Couveignes, J.-M.: Computing isogenies in low characteristic, Thesis Bordeaux1994. To appear. 
  10. [10] Elkies, N.D.: Explicit Isogenies, manuscript, Boston MA, 1992. 
  11. [11] Hartshorne, R.: Algebraic Geometry, Graduate Texts in Math. 52, Springer-Verlag, BerlinHeidelbergNew York1977. Zbl0367.14001MR463157
  12. [12] Lang, S.: Elliptic .Functions, Addison-Wesley, Reading MA1973. Zbl0316.14001MR409362
  13. [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. [14] Lenstra, H.W.: Elliptic curves and number-theoretical algorithms, Proc. of the International Congress of Math., Berkeley1986, 99-120. Zbl0686.14039MR934218
  15. [15] Lenstra, H.W.: Letter to H. Cohen, August 16, 1990. 
  16. [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. [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. [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. [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. [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. [21] Silverman, J.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer-Verlag, BerlinHeidelbergNew York1986. Zbl0585.14026MR817210

Citations in EuDML Documents

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.