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 Free Access

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?)

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