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_0(X)_{p^n}$ by $O(n^2 \log p)$ operations in $k$. This generalizes a result of Semaev for elliptic curves to curves of arbitrary genus.