A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus over GF(q)
There are well-known subexponential algorithms for finding discrete logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adapt able for finding discrete logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves, except for very special cases (Menezes ct al., IEEE Trans. Inform. Theory 39 (1993) 1639-1646, Okamoto and Sakurai, Lecture Notes in Computer Science, vol. 576, Springer, Berlin, 1991). This has led to the development of cryptographic systems based on the discrete logarithm problem for such groups (Koblitz, Math. Comput. 48 (1987) 203-209, J. Cryptogr. 1 (1989) 139-150, Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer, Dordrecht, 1993, Miller, Lecture Notes in Computer Science, Springer, Berlin, 1986, pp. 417-426). In this paper a subexponential algorithm is presented for finding discrete logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over prime fields. We give a heuristic argument that under certain assumptions, there exists a constant c less than or equal to 2.181 such that for g is an element of Z(>0) and odd prime powers q with log q less than or equal to (2g + 1)(1-epsilon) and 0 < epsilon = o(1), the algorithm computes discrete logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(q) of the form y(2) = f(x) with deg(f) = 2g+1, within expected time Lq2g+1[1/2,c], or equivalently, L-qg[1/2,c'] with c' =root 2c. (C) 1999 Elsevier Science B.V. All rights reserved.
subexponential algorithms discrete logarithm elliptic and hyperelliptic curves