ON THE DISCRETE LOGARITHM PROBLEM IN CLASS GROUPS OF CURVES

We study the discrete logarithm problem in degree 0 class groups of curves over finite fields, with particular emphasis on curves of small genus. We prove that for every fixed g >= 2, the discrete logarithm problem in degree 0 class groups of curves of genus g can be solved in an expected time of a (O) over tilde (q(2-2/g)), where F-q, is the ground field. This result generalizes a corresponding result for hyperelliptic curves given in imaginary quadratic representation with cyclic degree 0 class group, and just as this previous result, it is obtained via an index calculus algorithm with double large prime variation. Generalizing this result, we prove that for fixed g(0) >= 2 the discrete logarithm problem in class groups of all curves C/F-q of genus g >= g(0) can be solved in an expected time of (O) over tilde((q(g))(2/g0(1- 1/g0))) and in an expected time of (O) over tilde(#Cl-0(C)(2/g0(1 - 1/g0))). As a complementary result we prove that for any fixed n is an element of N with n >= 2 the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields F-qn, q a prime power, can be solved in an expected time of (O) over tilde (q(2-2/n)). Furthermore, we give an algorithm for the efficient construction of a uniformly randomly distributed effective divisor of a specific degree, given the curve and its L-polynomial.