On the discrete logarithm problem for plane curves (Q1940471): Difference between revisions

This paper is concerned with the complexity of the discrete logarithm problem in degree \(0\) class groups of curves over finite fields. The curves are assumed to be given by plane models and the complexity is expressed in terms of the degree \(d\) of the model and the cardinality \(q\) of the ground field. For non-hyperelliptic genus \(3\) curves (given by a smooth plane model of degree \(d=4\)) it is proved that the discrete logarithm problem can be solved in an expected time of \(\tilde{O}(q)\). This improves the estimation of \(\tilde{O}\left(q^{2-(2/g)}\right)=\tilde{O}(q^{4/3})\), obtained by the author in [Math. Comput. 80, No. 273, 443--475 (2011; Zbl 1231.11142)]. For the general case of degree \(d\geq4\), an estimation of \(\tilde{O}\left(q^{2-(2/(d-2))}\right)\) is obtained, under the assumption that there exists a line cutting the curve in a divisor which splits completely into distinct \(\mathbb{F}_q\)-rational points. In particular, this estimation holds for curves given by reflexive plane models. The algorithms follow the index calculus strategy. The factor base is a subset of the set of \(\mathbb{F}_q\)-rational points of the curve and the ``double large prime variation'' technique is used to reduce the cost of finding sufficiently many relations.