Index calculus with double large prime variation for curves of small genus with cyclic class group

Abstract

We present an index calculus algorithm with double large prime variation which lends itself well to a rigorous analysis. Using this algorithm we prove that for fixed genus $g\ge 2$, the discrete logarithm problem in degree 0 class groups of non-singular curves over finite fields ${\mathbb{F}}_q$ can be solved in an expected time of $\tilde{O}(q^{2-2/g})$, provided that the curve is given by a plane model of bounded degree and the degree 0 class group is cyclic. The result generalizes a previous result for hyperelliptic curves given by an imaginary Weierstraß equation obtained by Gaudry, Thomé, Thériault and the author.