Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques

François Morain

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

  • Volume: 7, Issue: 1, page 255-282
  • ISSN: 1246-7405

Abstract

top
We describe the algorithms that are needed for an efficient implementation of Schoof’s method for computing the number of points on en elliptic curve over a finite field. We try to unify the ideas of Atkin and Elkies. In particular, we describe the computation of equations for X 0 ( ℓ ) , ℓ a prime number, as well as the efficient computation of factors of the division polynomials of an elliptic curve.

How to cite

top

Morain, François. "Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques." Journal de théorie des nombres de Bordeaux 7.1 (1995): 255-282. <http://eudml.org/doc/247643>.

@article{Morain1995,
abstract = {Nous décrivons dans cet article les algorithmes nécessaires à une implantation efficace de la méthode de Schoof pour le calcul du nombre de points sur une courbe elliptique dans un corps fini. Nous tentons d’unifier pour cela les idées d’Atkin et d’Elkies. En particulier, nous décrivons le calcul d’équations pour $X_0 (\ell )$, $\ell $ premier, ainsi que le calcul efficace de facteurs des polynômes de division d’une courbe elliptique.},
author = {Morain, François},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {courbes elliptiques; corps finis; algorithme de Schoof; formes modulaires; équations modulaires; polynômes de division; factors of division polynomials; Schoof's algorithm; number of rational points; elliptic curve; prime field; modular curves},
language = {fre},
number = {1},
pages = {255-282},
publisher = {Université Bordeaux I},
title = {Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques},
url = {http://eudml.org/doc/247643},
volume = {7},
year = {1995},
}

TY - JOUR
AU - Morain, François
TI - Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques
JO - Journal de théorie des nombres de Bordeaux
PY - 1995
PB - Université Bordeaux I
VL - 7
IS - 1
SP - 255
EP - 282
AB - Nous décrivons dans cet article les algorithmes nécessaires à une implantation efficace de la méthode de Schoof pour le calcul du nombre de points sur une courbe elliptique dans un corps fini. Nous tentons d’unifier pour cela les idées d’Atkin et d’Elkies. En particulier, nous décrivons le calcul d’équations pour $X_0 (\ell )$, $\ell $ premier, ainsi que le calcul efficace de facteurs des polynômes de division d’une courbe elliptique.
LA - fre
KW - courbes elliptiques; corps finis; algorithme de Schoof; formes modulaires; équations modulaires; polynômes de division; factors of division polynomials; Schoof's algorithm; number of rational points; elliptic curve; prime field; modular curves
UR - http://eudml.org/doc/247643
ER -

References

top
  1. [1] A.O.L. Atkin, The number of points on an elliptic curve modulo a prime, Manuscrit, 1988. 
  2. [2] A.O.L. Atkin,, The number of points on an elliptic curve modulo a prime (ii), Manuscrit, 1992. 
  3. [3] B. J. Birch et W. Kuyk (Réd.), Modular functions of one variable IV, Lecture Notes in Math., vol. 476, Springer, 1975, Proceedings International Summer School University of Antwerp, RUCA, July 17-Agust 3, 1972. Zbl0315.14014MR376533
  4. [4] L.S. Charlap, R. Coley, et D.P. Robbins, Enumeration of rational points on elliptic curves over finite fields, Manuscrit, 1991. 
  5. [5] J.-M. Couveignes et F. Morain, Schoof 's algorithm and isogeny cycles, ANTS-I (L. Adleman et M.-D. Huang, Réd.), Lecture Notes in Comput. Sci., vol. 877, Springer-Verlag, 1994, p. 43-58. Zbl0849.14024MR1322711
  6. [6] J.-M. Couveignes, Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, juillet 1994. 
  7. [7] P. Deligne et M. Rapoport, Les schémas de modules de courbes elliptiques, Modular functions of one variable II (P. Deligne et W. Kuyk, Réd.), Lecture Notes in Math., vol. 349, Springer, 1973, Proceedings International Summer School University of Antwerp, RUCA, July 17-Agust 3, 1972, p. 143-316. Zbl0281.14010MR337993
  8. [8] P. Deligne et J.P., Serre, Formes modulaires de poids 1, Ann. scient. Éc. Norm. Sup.7 (1974), 507-530. Zbl0321.10026MR379379
  9. [9] L. Dewaghe, Remarques sur l'algorithme SEA, en préparation, décembre 1994. 
  10. [10] Noam D. Elkies, Explicit isogenies, Manuscrit, 1991. 
  11. [11] R. Fricke, Lehrbuch der Algebra, III, F. Vieweg and Sohn, Braunschweig, 1928. 
  12. [12] D.E. Knuth, The Art of Computer Programming: Seminumerical algorithms, Addison-Wesley, 1981. Zbl0477.65002MR633878
  13. [13] F. Lehmann, M. Maurer, V. Müller, et V. Shoup, Counting the number of points on elliptic curves over finite fields of characteristic greater than three, ANTS-I (L. Adleman et M.-D. Huang, Réd.), Lecture Notes in Comput. Sci., vol. 877, Springer-Verlag, 1994, p. 60-70. Zbl0839.11026MR1322712
  14. [14] R. Lercier et F. Morain, Counting points on elliptic curves over Fpn using Couveignes's algorithm, Rapport de Recherche LIX/RR/95/09, École Polytechnique, septembre 1995. 
  15. [15] R. Lercier et F. Morain, Counting the number of points on elliptic curves over finite fields: strategies and performances, Advances in Cryptology- EUROCRYPT'95 (L. C. GUILLOU et J.-J. QUISQUATER, réd.), Lecture Notes in Comput. Sci., no. 921, 1995, p. 79-94. Zbl0903.11029MR1367512
  16. [16] K. Mahler, On a class of non-linear functionat equations connected with modular functions, J. Austral. Math. Soc. Ser. A22 (1976), 65-120. Zbl0345.39002MR441867
  17. [17] B. Mazur, Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math.47 (1977), 33-186. Zbl0394.14008MR488287
  18. [18] V. Müller, Looking for the eigenvalue in Schoof's algorithm, en préparation, octobre 1994. 
  19. [19] B. Schoeneberg, Elliptic modular functions, Die Grundlehren der mathema tischen Wissenschaften in Einzeldarstellungen, vol. 203, Springer-Verlag, 1974. Zbl0285.10016MR412107
  20. [20] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp.44 (1985), 483-494. Zbl0579.14025MR777280
  21. [21] René Schoof, Counting points on elliptic curves over finite fields, J. Théorie des Nombres de Bordeaux, 7 (1995), 219-254. Zbl0852.11073MR1413578
  22. [22] J.H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer,1986. Zbl0585.14026MR817210

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.