Finding Secure Curves with the Satoh-FGH Algorithm and an Early-Abort Strategy

  • Mireille Fouquet
  • Pierrick Gaudry
  • Robert Harley
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


The use of elliptic curves in cryptography relies on the ability to count the number of points on a given curve. Before 1999, the SEA algorithm was the only efficient method known for random curves. Then Satoh proposed a new algorithm based on the canonical p-adic lift of the curve for p ≥ 5. In an earlier paper, the authors extended Satoh's method to the case of characteristics two and three. This paper presents an implementation of the Satoh-FGH algorithm and its application to the problem of findingcurv es suitable for cryptography. By combining Satoh-FGH and an early-abort strategy based on SEA, we are able to find secure random curves in characteristic two in much less time than previously reported. In particular we can generate curves widely considered to be as secure as RSA-1024 in less than one minute each on a fast workstation.


Elliptic Curve Elliptic Curf Field Size Discrete Logarithm Torsion Point 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. FIPS186.
    FIPS 186-2. Digital Signature Standard. Federal Information Processing Standards publication, january 2000. U.S. Departement of Commerce/National Institute of Standards and Technology. Available at
  2. P1363.
    IEEE P1363. Standard specifications for public key cryptography. Available at
  3. Atk92.
    A. O. L. Atkin. The number of points on an elliptic curve modulo a prime. Series of e-mails to the NMBRTHRY mailinglist, 1992.Google Scholar
  4. BSS99.
    I. Blake, G. Seroussi, and N. Smart. Elliptic curves in cryptography, volume 265 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1999.Google Scholar
  5. Coh96.
    H. Cohen. A course in algorithmic algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, 1996. Third printing.Google Scholar
  6. Cou94.
    J.-M. Couveignes. Quelques calculs en théorie des nombres. Thése, Université de Bordeaux I, July 1994.Google Scholar
  7. Cou96.
    J.-M. Couveignes. Computing l-isogenies using the p-torsion. In H. Cohen, editor, Algorithmic Number Theory, volume 1122 of Lecture Notes in Comput. Sci., pages 59–65. Springer Verlag, 1996. Second International Symposium, ANTS-II, Talence, France, May 1996, Proceedings.Google Scholar
  8. Dew98.
    L. Dewaghe. Remarks on the Schoof-Elkies-Atkin algorithm. Math. Comp., 67(223):1247–1252, July 1998.zbMATHCrossRefMathSciNetGoogle Scholar
  9. DGM99.
    I. Duursma, P. Gaudry, and F. Morain. Speeding up the discrete log computation on curves with automorphisms. In Kwok Yan Lam, Eiji Okamoto, and Chaoping Xing, editors, Advances in Cryptology-ASIACRYPT '99, volume 1716 of Lecture Notes in Comput. Sci., pages 103–121. Springer-Verlag, 1999. International Conference on the Theory and Applications of Cryptology and Information Security, Singapore, November 1999, Proceedings.Google Scholar
  10. Elk98.
    N. Elkies. Elliptic and modular curves over finite fields and related computational issues. In D.A. Buell and eds. J.T. Teitelbaum, editors, Computational Perspectives on Number Theory, pages 21–76. AMS/International Press, 1998. Proceedings of a Conference in Honor of A.O.L. Atkin.Google Scholar
  11. FGH00.
    M. Fouquet, P. Gaudry, and R. Harley. An extension of Satoh’s algorithm and its implementation. J. Ramanujan Math. Soc., 15:281–318, 2000.zbMATHMathSciNetGoogle Scholar
  12. FR94.
    G. Frey and H.-G. Rück. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp., 62(206):865–874, April 1994.zbMATHCrossRefMathSciNetGoogle Scholar
  13. GHS00.
    P. Gaudry, F. Hess, and N. Smart. Constructive and destructive facets of Weil descent on elliptic curves. Submitted to J. Crypt. and available at, 2000.
  14. GLV.
    R. Gallant, R. Lambert, and S. Vanstone. Improving the parallelized Pollard lambda search on binary anomalous curves. To appear in Math. Comp. Google Scholar
  15. Har00.
  16. Has33.
    H. Hasse. Beweis des Analogons der Riemannschen Vermutung für die Artinschen und F. K. Smidtschen Kongruenzzetafunktionen in gewissen elliptischen Fällen. Ges. d. Wiss. Narichten. Math.-Phys. Klasse, pages 253–262, 1933.Google Scholar
  17. IKNY98.
    T. Izu, J. Kogure, M. Noro, and K. Yokoyama. Efficient implementation of Schoof’s algorithm. In K. Ohta and D. Pei, editors, Advances in Cryptology-ASIACRYPT '98, volume 1514 of Lecture Notes in Comput. Sci., pages 66–79. Springer-Verlag, 1998. International Conference on the theory and application of cryptology and information security, Beijing, China, October 1998.CrossRefGoogle Scholar
  18. JM99.
    D. Johnson and A. Menezes. The elliptic curve digital signature algorithm (ECDSA). Technical Report CORR 99-34, U. Waterloo, 1999. Available at
  19. Kob87.
    N. Koblitz. Elliptic curve cryptosystems. Math. Comp., 48(177):203–209, January 1987.zbMATHCrossRefMathSciNetGoogle Scholar
  20. Ler97a.
    R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. Thése, École polytechnique, June 1997.Google Scholar
  21. Ler97b.
    R. Lercier. Finding good random elliptic curves for cryptosystems defined over \( \mathbb{F}_{{\text{2}}^{\text{n}} } \) . In W. Fumy, editor, Advances in Cryptology-EUROCRYPT '97, volume 1233 of Lecture Notes in Comput. Sci., pages 379–392. Springer-Verlag, 1997. International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 1997, Proceedings.Google Scholar
  22. LM95.
    R. Lercier and F. Morain. Counting the number of points on elliptic curves over finite fields: strategies and performances. In L. C. Guillou and J.-J. Quisquater, editors, Advances in Cryptology-EUROCRYPT '95, volume 921 of Lecture Notes in Comput. Sci., pages 79–94, 1995. International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 1995, Proceedings.Google Scholar
  23. LST64.
    J. Lubin, J. P. Serre, and J. Tate. Elliptic curves and formal groups. In Lecture notes prepared in connection with the seminars held at the Summer Institute on Algebraic Geometry, Whitney Estate, Woods Hole, Massachusetts, July 6–July 31, 1964, 1964. Scanned copies available at
  24. LV00.
    A. Lenstra and E. Verheul. Selecting cryptographic key sizes, January 2000. Presented at PKC2000.Google Scholar
  25. Men93.
    A. J. Menezes. Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993.Google Scholar
  26. Mil87.
    V. Miller. Use of elliptic curves in cryptography. In A. M. Odlyzko, editor, Advances in Cryptology-CRYPTO '86, volume 263 of Lecture Notes in Comput. Sci., pages 417–426. Springer-Verlag, 1987. Proceedings, Santa Barbara (USA), August 11–15, 1986.Google Scholar
  27. Mor95.
    F. Morain. Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques. J. Théor. Nombres Bordeaux, 7:255–282, 1995.zbMATHMathSciNetGoogle Scholar
  28. MOV91.
    A. Menezes, T. Okamoto, and S. A. Vanstone. Reducing elliptic curves logarithms to logarithms in a finite field. In Proceedings 23rd Annual ACM Symposium on Theory of Computing (STOC), pages 80–89. ACM Press, 1991. May 6–8, New Orleans, Louisiana.Google Scholar
  29. MP98.
    V. Müller and S. Paulus. On the generation of cryptographically strong elliptic curves. Preprint, 1998.Google Scholar
  30. Mül95.
    V. Müller. Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik grö̈ser drei. PhD thesis, University of Saarland, 1995.Google Scholar
  31. PH78.
    S. Pohlig and M. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Trans. Inform. Theory, IT-24:106–110, 1978.CrossRefMathSciNetGoogle Scholar
  32. Pol78.
    J. M. Pollard. Monte Carlo methods for index computation mod p. Math. Comp., 32(143):918–924, July 1978.zbMATHCrossRefMathSciNetGoogle Scholar
  33. SA98.
    T. Satoh and K. Araki. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. St. Paul., 47:81–92, 1998.zbMATHMathSciNetGoogle Scholar
  34. Sat00.
    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
  35. Sch85.
    R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp., 44:483–494, 1985.zbMATHCrossRefMathSciNetGoogle Scholar
  36. Sch95.
    R. Schoof. Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux, 7:219–254, 1995.zbMATHMathSciNetGoogle Scholar
  37. Sem98.
    I. A. Semaev. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curves in characteristic p. Math. Comp., 67(221):353–356, January 1998.zbMATHCrossRefMathSciNetGoogle Scholar
  38. Ser68.
    J. P. Serre. Corps locaux. Hermann, 1968.Google Scholar
  39. Sil86.
    J. H. Silverman. The arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics. Springer-Verlag, 1986.Google Scholar
  40. Sil00.
    R. Silverman. A cost-based security analysis of symmetric and assymetric key lengths.. Bulletin Number 13 of RSA Security, April 2000.Google Scholar
  41. Skj.
    B. Skjernaa. Satoh’s algorithm in characteristic 2. Copies available at
  42. Sma99.
    N. Smart. The discrete logarithm problem on elliptic curves of trace one. J. Cryptology, 12:193–196, 1999.zbMATHCrossRefMathSciNetGoogle Scholar
  43. Vél71.
    J. Vélu. Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. I Math., 273:238–241, July 1971. Série A.zbMATHGoogle Scholar
  44. vOW99.
    P. C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic applications. J. of Cryptology, 12:1–28, 1999.zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Mireille Fouquet
    • 1
  • Pierrick Gaudry
    • 1
  • Robert Harley
    • 2
  1. 1.LIX, École polytechniquePalaiseau CedexFrance
  2. 2.ArgoTechParisFrance

Personalised recommendations