| Clauss Diem |  |
 |
Date of the talk: 11 May 2012
Computing discrete logarithms with pencils
We study the discrete logarithm problem in the degree 0 class groups of curves $\mathcal{C}$ of a fixed genus over finite fields $\mathbb{F}_q$. We consider the usual index calculus method to compute discrete logarithms, and for this we want to compute suitable relations. We observe that any non-constant function on $\mathcal{C}$ leads to a relation. Moreover, we not only have one relation (given by the associated principal divisor) but in fact all preimages of closed points of $\mathbb{P}^1_{\mathbb{F}_q}$ in $\mathcal{C}$ are linearly equivalent. They form what is called a pencil. By using such pencils, we obtain the following heuristic result:Let a natural number $g \geq 5$ be fixed. Then the discrete logarithm problem for nearly all curves of genus $g$ can be solved in an expected time of $$ \tilde{O}(q^{2 - \frac{2}{g-2}}) \; . $$
This improves upon a previous algorithm which is based on the intersection of a plane model of the curve with lines. The improvement corresponds to the drop of the genus by 1.
