On the discrete logarithm problem in class groups of curves
Claus Diem · Mathematics of Computation · 2010
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 g \geq 2 , the discrete logarithm problem in degree 0 class groups of curves of genus g g can be solved in an expected time of O ~ ( q 2 − 2 g ) \tilde {\mathcal {O}}(q^{2 - \frac {2}{g}}) , where F q \mathbb {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 g_0 \geq 2 the discrete logarithm problem in class groups of all curves C / F q \mathcal {C}/\mathbb {F}_q of genus g ≥ g 0 g \geq g_0 can be solved in an expected time of O ~ ( ( q g ) 2 g 0 ( 1