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

Author:
Open Access
Publisher website
Google Scholar
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 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.

This publication has 17 references indexed in Scilit: