Paper 2005/119

Index Calculus in Class Groups of Plane Curves of Small Degree

Claus Diem

Abstract

We present a novel index calculus algorithm for the discrete logarithm problem (DLP) in degree 0 class groups of curves over finite fields. A heuristic analysis of our algorithm indicates that asymptotically for varying q, ``essentially all'' instances of the DLP in degree 0 class groups of curves represented by plane models of a fixed degree d over ${\mathbb{F}}_q$ can be solved in an expected time of $\tilde{O}(q^{2-2/(d-2)})$. A particular application is that heuristically, ``essentially all'' instances of the DLP in degree 0 class groups of non-hyperelliptic curves of genus 3 (represented by plane curves of degree 4) can be solved in an expected time of $$. We also provide a method to represent ``sufficiently general'' (non-hyperelliptic) curves of genus $$ by plane models of degree $$. We conclude that on heuristic grounds the DLP in degree 0 class groups of ``sufficiently general'' curves of genus $$ (represented initially by plane models of bounded degree) can be solved in an expected time of $$.