The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic (Q1671640): Difference between revisions

The paper under review deals with the discrete logarithm problem in the divisor class group \(\mathrm{Jac}(C)\) of a hyperelliptic curve or an elliptic curve \(C\) defined over a finite field. The computation of discrete logarithms in such groups can be done using a variant of the Index-Calculus algorithm called a decomposition attack. Such algorithms run in two phases. This paper focus in the first one, called relations collection or harvesting. In this phase, a linear system is built by finding linear relations between the discrete logarithms of elements of a special subset, the so-called factor base. These relations can be found by solving multiple instances of the Point m-Decomposition Problem (\(PDP_m\)) which is the following: Given an element \(R\) and a subset \(B\) of \(\mathrm{Jac}(C)\), find, if they exist, \(D_1,\ldots,D_m\in B\) such that \(R=D_1+\cdots+D_m\). In [\textit{G. Hanrot} (ed.) et al., Algorithmic number theory. 9th international symposium, ANTS-IX, Nancy, France, July 19--23, 2010. Proceedings. Berlin: Springer (2010; Zbl 1196.11006)] a method is proposed for solve instances of this problem by describing decompositions using functions in suitable Riemann-Roch spaces. When the curve \(C\) is elliptic, an alternate approach involving Weil descent on summation polynomials can also be used. The general goal of this paper is to design an efficient method for solving \(PDP_m\) instances. For this task, the authors propose new techniques to reduce the degree of the systems obtained from the harvesting in even characteristic. They develop in parallel methods which deal with Nagao's approach and with summation approach as well. Finally, they compare them, adding their new degree reduction algorithm, to determine which is more efficient when \(C\) has genus \(> 1\). Finally, Nagao's approach is used to estimate the total running time for the harvesting on a binary genus 2 curve with class group of around \(2^{184}\) elements.