Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time

Author: Andreas Enge
Journal: Math. Comp. 71 (2002), 729-742
MSC (2000): Primary 68Q25, 14H40, 11T71; Secondary 11G25, 14K15
Published electronically: November 14, 2001
MathSciNet review: 1885624
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We provide a subexponential algorithm for solving the discrete logarithm problem in Jacobians of high-genus hyperelliptic curves over finite fields. Its expected running time for instances with genus $g$ and underlying finite field $\mathbb{F} _q$ satisfying $g \geq \vartheta \log q$ for a positive constant $\vartheta$ is given by

\begin{displaymath}O \left( e^{ \left( \frac {5}{\sqrt 6} \left( \sqrt {1 + \fra... ...) + o (1) \right) \sqrt {(g \log q) \log (g \log q)}} \right). \end{displaymath}

The algorithm works over any finite field, and its running time does not rely on any unproven assumptions.

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

  • 1. Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields, Lecture Notes in Comput. Sci., 877, Springer, Berlin, 1994, pp. 28-40. MR 96b:11078
  • 2. Leonard M. Adleman and Ming-Deh Huang (eds.), Algorithmic number theory, Lecture Notes in Comput. Sci., 877, Springer-Verlag, Berlin, 1994. MR 95j:11119
  • 3. E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen II, Math. Z. 19 (1924), 207-246.
  • 4. Johannes Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Progr. Math. 91, Birkhäuser, Boston, 1990, pp. 27-41. MR 92g:11125
  • 5. David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95-101. MR 88f:11118
  • 6. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Math., Springer-Verlag, Berlin, 1993. MR 94i:11105
  • 7. Henri Cohen (ed.), Algorithmic number theory -- Ants-II, Lecture Notes in Comput. Sci., vol. 1122, Springer-Verlag, Berlin, 1996. MR 97k:11001
  • 8. P. D. Domich, R. Kannan, and L. E. Trotter Jr., Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), no. 1, 50-59. MR 88e:65047
  • 9. Stephan Düllmann, Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen, Dissertation, Universität des Saarlandes, Saarbrücken, 1991.
  • 10. Andreas Enge, The extended Euclidian algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems, Des. Codes Cryptogr., 23 (2001), 53-74. CMP 2001:11
  • 11. -, Hyperelliptic cryptosystems: Efficiency and subexponential attacks, Dissertation, Universität Augsburg, 2000, ISBN 3-8311-1868-X.
  • 12. -, How to distinguish hyperelliptic curves in even characteristic, to appear in Proceedings of the Conference on Public Key Cryptography and Computational Number Theory, Warszawa 2000.
  • 13. Andreas Enge and Andreas Stein, Smooth ideals in hyperelliptic function fields, Math. Comp., posted on October 4, 2001, PII S0025-5718(01)01352-7 (to appear in print).
  • 14. Ralf Flassenberg and Sachar Paulus, Sieving in function fields, Experiment. Math. 8 (1999), no. 4, 339-349. MR 2000j:11179
  • 15. Catherine Goldstein (ed.), Séminaire de théorie des nombres, Paris 1988-1989, Progress in Mathematics, Birkhäuser, Boston, 1990. MR 91k:11004
  • 16. Ming-Deh Huang and Doug Ierardi, Counting points on curves over finite fields, J. Symbolic Comput. 25 (1998), 1-21. MR 98i:11040
  • 17. Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), 139-150. MR 90k:11165
  • 18. -, Algebraic aspects of cryptography, Algorithms Comput. Math., vol. 3, Springer-Verlag, Berlin, 1998. MR 2000a:94012
  • 19. A. K. Lenstra, Fast and rigorous factorization under the generalized Riemann hypothesis, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), 443-454. MR 90a:11152
  • 20. Kevin S. McCurley, Cryptographic key distribution and computation in class groups, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459-479. MR 92e:11149
  • 21. Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato, An elementary introduction to hyperelliptic curves, Springer-Verlag, 1998, pp. 155-178. MR 2000a:94012
  • 22. Richard A. Mollin (ed.), Number theory and applications, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 265, Kluwer Acad. Publ., Dordrecht, 1989. MR 92c:11002
  • 23. Achim Müller, Effiziente Algorithmen für Probleme der linearen Algebra über $\mathbb{Z} $, Diplomarbeit, Universität des Saarlandes, Saarbrücken, 1994.
  • 24. Volker Müller, Andreas Stein, and Christoph Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus, Math. Comp. 68 (1999), no. 226, 807-822. MR 99i:11119
  • 25. J. Pila, Frobenius maps of Abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745-763. MR 91a:11071
  • 26. Bjorn Poonen, Computational aspects of curves of genus at least $2$, Lecture Notes in Comput. Sci., 1122, Springer, Berlin, 1996, pp. 283-306. MR 98c:11059
  • 27. Andreas Stein, Algorithmen in reell-quadratischen Kongruenzfunktionenkörpern, Dissertation, Universität des Saarlandes, Saarbrücken, 1996.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68Q25, 14H40, 11T71, 11G25, 14K15

Retrieve articles in all journals with MSC (2000): 68Q25, 14H40, 11T71, 11G25, 14K15

Additional Information

Andreas Enge
Affiliation: Mathematisches Institut, Universität Augsburg, 86135 Augsburg, Germany
Address at time of publication: LIX, École Polytechnique, 91128 Palaiseau Cedex, France

Keywords: Subexponentiality, discrete logarithm, Jacobian, hyperelliptic curve
Received by editor(s): March 10, 1999
Received by editor(s) in revised form: June 5, 2000
Published electronically: November 14, 2001
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society