A Memory Efficient Version of Satoh’s Algorithm

  • Frederik Vercauteren
  • Bart Preneel
  • Joos Vandewalle
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


In this paper we present an algorithm for counting points on elliptic curves over a finite field \( \mathbb{F}_{p^n } \) of small characteristic, based on Satoh's algorithm. The memory requirement of our algorithm is O(n2), where Satoh's original algorithm needs O(n 3) memory. Furthermore, our version has the same run time complexity of O(n n+ε) bit operations, but is faster by a constant factor. We give a detailed description of the algorithm in characteristic 2 and show that the amount of memory needed for the generation of a secure 200-bit elliptic curve is within the range of current smart card technology.


elliptic curve finite field order counting Satoh’s algorithm 


  1. 1.
    A.O.L. Atkin. The number of points on an elliptic curve modulo a prime. Series of e-mails to the NMBRTHRY mailing list, 1992.Google Scholar
  2. 2.
    J.M. Couveignes. Quelques calculs en théorie des nombres. PhD thesis, Université de Bordeaux, 1994.Google Scholar
  3. 3.
    J.M. Couveignes. Computing l-isogenies with the p-torsion. ANTS-II, Lecture Notes in Comp. Sci., 1122:59–65, 1996.Google Scholar
  4. 4.
    J.A. Csirik. Counting the number of points on an elliptic curve on a low-memory device. 1998. Preprint.Google Scholar
  5. 5.
    M. Deuring. Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Abh. Math. Sem. Univ. Hamburg, 14:197–272, 1941.CrossRefMathSciNetGoogle Scholar
  6. 6.
    N. Elkies. Elliptic and modular curves over finite fields and related computational issues. Computational Perspectives on Number Theory, pages 21–76, 1998.Google Scholar
  7. 7.
    M. Fouquet, P. Gaudry, and R. Harley. On Satoh’s algorithm and its implementation. J. Ramanujan Math. Soc., 15:281–318, 2000.zbMATHMathSciNetGoogle Scholar
  8. 8.
    H. Hasse. Beweis des Analogons der Riemannschen Vermutung für die Artinschen und F. K. Smidtschen Kongruenzzetafunctionen in gewissen elliptischen Fällen. Ges. d. Wiss. Nachrichten. Math.-Phys. Klasse, pages 253–262, 1933.Google Scholar
  9. 9.
    R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. PhD thesis, L'École Polytechnique, Laboratoire D'Informatique, CNRS, Paris, June 1997.Google Scholar
  10. 10.
    J. Lubin, J.P. Serre, and J. Tate. Elliptic curves and formal groups. Lecture notes prepared in connection with the seminars held at the Summer Institute on Algebraic Geometry, Whitney Estate, Woods Hole, Massachusetts, 1964.Google Scholar
  11. 11.
    T. Satoh. The canonical lift of an ordinary elliptic curve over a finite field and its point counting. J. Ramanujan Math. Soc., 15:247–270, 2000.zbMATHMathSciNetGoogle Scholar
  12. 12.
    R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comput., 44:483–494, 1985.zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    J.P. Serre. Local Fields, volume 67 of Graduate Texts in Mathematics. Springer-Verlag, 1979.Google Scholar
  14. 14.
    B. Skjernaa. Satoh’s algorithm in characteristic 2. Preprint, 2000.Google Scholar
  15. 15.
    J. Vélu. Isogénies entre courbes elliptiques. C.R. Acad. Sc. Paris, 273:238–241, 1971.zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Frederik Vercauteren
    • 1
  • Bart Preneel
    • 1
  • Joos Vandewalle
    • 1
  1. 1.Dept. Elektrotechniek-ESAT/COSICK.U. LeuvenLeuven-HeverleeBelgium

Personalised recommendations