Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Constructing hyperelliptic curves of genus 2 suitable for cryptography

Author: Annegret Weng
Journal: Math. Comp. 72 (2003), 435-458
MSC (2000): Primary 11Y16, 11Y40, 94A60; Secondary 14K22, 14H45
Published electronically: May 3, 2002
MathSciNet review: 1933830
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this article we show how to generalize the CM-method for elliptic curves to genus two. We describe the algorithm in detail and discuss the results of our implementation.

References [Enhancements On Off] (What's this?)

  • 1. A.O.L. Atkin, The number of points on an elliptic curve modulo a prime, unpublished manuscript, 1991.
  • 2. A.O.L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68. MR 93m:11136
  • 3. J. von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), 187-224. MR 94d:12011
  • 4. P. Gaudry and R. Harley, Counting points on hyperelliptic curves over finite fields, ANTS IV (2000), 313-332.
  • 5. J.I.. Igusa, Arithmetic variety of moduli of genus two, Ann. of Math. 72 (1960), 612-649. MR 22:5637
  • 6. D.E. Knuth, The art of computer programming vol.2, seminumerical algorithms, Addison-Weseley, 1981. MR 83i:68003
  • 7. N. Koblitz, Primality of the number of points on an elliptic curve over a finite field, Pacific J. Math. 131 (1988), 157-165. MR 89h:11023
  • 8. -, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), 139-150. MR 90k:11165
  • 9. S. Lang, Introduction to algebraic and abelian functions, 2nd ed., Springer-Verlag, 1982. MR 84m:14032
  • 10. -, Complex multiplication, Springer-Verlag, 1983. MR 85f:11042
  • 11. S. Louboutin and R. Okazaki, Determination of all non-normal quartic cm-fields and of all non-abelian normal octic cm-fields with class number one, Acta Arith. (1994), 47-62. MR 95g:11107
  • 12. J.-F. Mestre, Construction des courbes de genre 2 a partir de leurs modules, Effective Methods in Algebraic Geometry (Castiglioncello, 1990), Prog. Math., Birkhäuser 94 (1991), 313-334. MR 92g:14022
  • 13. D. Mumford, Tata lecture on theta, vol. 1, Birkhäuser, 1983. MR 85h:14026
  • 14. -, Tata lecture on theta, vol. 2, Birkhäuser, 1984. MR 86b:14017
  • 15. R. Okazaki, On evaluation of ${L}$-functions over real quadratic fields, J. Math. Kyoto Univ. 31-4 (1991), 1125-1153. MR 93b:11154
  • 16. S. Paulus and A. Stein, Comparing real and imaginary arithmetics for divisor class groups of hyperelliptic curves, ANTS III, LNCS 1423 (1998), 576-591. MR 2000i:11098
  • 17. E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Cambridge University Press, 1989. MR 92b:11074
  • 18. S. Pohlig and M. Hellmann, An improved algorithm for computing logarithms over ${GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), 106-110.
  • 19. G. Shimura, Abelian varieties with complex multiplication and modular functions, revised ed., Princeton University Press, 1998. MR 99e:11076
  • 20. J.A. Solinas, Generalized Mersenne numbers, Technical Reports, CACR, Waterloo (1999).
  • 21. A.-M. Spallek, Kurven vom Geschlecht 2 und ihre Anwendung in Public-Key-Kryptosystemen, Ph.D. thesis, Institut für Experimentelle Mathematik, Universität GH Essen, 1994.
  • 22. P. van Wamelen, Examples of genus two cm curves defined over the rationals, Math. Comp. 68 (1999), 307-320. MR 99c:11079
  • 23. X. Wang, 2-dimensional simple factors of ${J}_0({N})$, Manuscripta Math. 87 (1995), 179-197. MR 96h:11059
  • 24. H.J. Weber, Hyperelliptic simple factors of ${J}_0({N})$ with dimension at least 3, Experiment. Math. 6 (1997), 273-287. MR 99e:14054

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11Y40, 94A60, 14K22, 14H45

Retrieve articles in all journals with MSC (2000): 11Y16, 11Y40, 94A60, 14K22, 14H45

Additional Information

Annegret Weng
Affiliation: Institute for Experimental Mathematics, University of Essen, D-45326 Essen, Germany

Received by editor(s): January 19, 2001
Received by editor(s) in revised form: March 29, 2001
Published electronically: May 3, 2002
Additional Notes: This work was supported by the NRW Forschungsverbund Datensicherheit (see and the DFG (Graduiertenkolleg).
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society