Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time
Andreas Enge · Mathematics of Computation · 2001
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 g and underlying finite field F q \mathbb {F}_q satisfying g ≥ ϑ log q g \geq \vartheta \log q for a positive constant ϑ \vartheta is given by \[ O ( e ( 5 6 ( 1 + 3 2 ϑ + 3 2 ϑ ) + o ( 1 ) ) ( g log q ) log ( g log q ) ) . O \left ( e^{ \left ( \frac {5}{\sqrt 6} \left ( \sqrt {1 + \frac {3}{2 \vartheta }} + \sqrt {\frac {3}{2 \vartheta }} \right ) + o (1) \right ) \sqrt {(g \log q) \log (g \log q)}} \right ). \] The algorithm works over any finite field, and its running time does not rely on any unproven assumptions.