Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields (Q2871193)

The discrete logarithm problem in the Jacobian of elliptic and hyperelliptic curves has been extensively proposed as basis of many public-key cryptographic protocols. An interesting application of high genus hyperelliptic curves is that Weil descent can reduce the discrete logarithm problem on some elliptic curves over a finite field of composite degree to an instance of the same problem on an hyperelliptic curve of high genus defined over a smaller field. Under some assumptions this problem can be solve in subexponential time using index calculus algorithms.NEWLINENEWLINEThe paper under review deals with the discrete logarithm problem in the Jacobian of high genus hyperelliptic curves defined over even characteristic finite fields and propose new improved versions of index-calculus algorithms. The first improvement is the incorporation of several ideas for the low-genus case given by \textit{P. Gaudry} [Lect. Notes Comput. Sci. 1807, 19--34 (2000; Zbl 1082.94517)] and \textit{N. Thériault} [Lect. Notes Comput. Sci. 2894, 75--92 (2003; Zbl 1205.94103)] and using a smaller factor basis into the algorithm of \textit{A. Enge} and \textit{P. Gaudry} [Acta Arith. 102, No. 1, 83--103 (2002; Zbl 1028.11079)]. The second improvement is the adaptation of of sieving techniques from \textit{R. Flassenberg} and \textit{S. Paulus} [Exp. Math. 8, No. 4, 339--349 (1999; Zbl 0942.11047)] and \textit{M. J. Jacobson jun.} [Math. Comput. 68, No. 226, 859--867 (1999; Zbl 1036.11067)].NEWLINENEWLINEThe resulting algorithms are applied to the same Weil descent examples as in [\textit{M. Jacobson} et al., J. Ramanujan Math. Soc. 16, No. 3, 231--260 (2001; Zbl 1017.11030)], showing that the proposed versions lead to improved performance in practice.