Index-calculus algorithms have two phases. First, we collect relations and after there is a systematic linear algebra phase. Most of the recent work focuses on refining the harvesting of the relations. When we compute with the Jacobian of algebraic curves, the usual way of collecting a relation is to compute a divisor and then to test for its smoothness. This requires a good understanding of the arithmetic on such Jacobian varieties.

In this talk we will recall the usual polynomial representation of elements in Jacobians and we will present a new way of finding a relation in the Jacobian of hyperelliptic curves defined on finite field, minimizing the arithmetic cost and generalizing the ideas of Diem for small degree curves. We will also discuss the complexity depending on the genus of the hyperelliptic curve.

Joint work with Jean-Charles Faugère and Vanessa Vitse.