Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time
Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time
复制标题
DOI：
10.1090/s0025-5718-01-01363-1
复制
发表时间：
2002-04
期刊：
影响因子：
--
通讯作者：
Andreas Enge
中科院分区：
文献类型：
--
作者：
Andreas Enge
给出了求解有限域上高亏格超椭圆曲线雅可比行列式离散对数问题的一个次指数算法。对于亏格为g的有限域Fq，其期望运行时间为O（e（f（1/2））+ o（1））<$（g log q）log（g log q））该算法适用于任何有限域，其运行时间不依赖于任何未经证明的假设。
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 Fq satisfying g ≥ ϑ log q for a positive constant ϑ is given by O(e(f(√1+3/2ϑ + √3/2ϑ) + o(1)) √(g log q) log (g log q)) The algorithm works over any finite field, and its running time does not rely on any unproven assumptions.