Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: enge@math.uni-augsburg.de, enge@lix.polytechnique.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-01-01363-1
PII: S 0025-5718(01)01363-1
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