On the discrete logarithm in the divisor class group of curves

Let X be a curve which is defined over a finite field k of characteristic p. We show that one can evaluate the discrete logarithm in Pic₀(X)pⁿ by O(n² log p) operations in k. This generalizes a result of Semaev for elliptic curves to curves of arbitrary genus.