Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms (Q2068384)

This paper proposes two variants of the Gaudry-Schost algorithm to attack the multidimensional discrete logarithm problem, variants improving the time cost.\par Giving a suitable finite abelian group \(G\)\, (for example the group of points of an elliptic curve defined over a finite group) the d-dimensional DLP asks, given \(g_1,\dots, g_d\in G\)\, elements of orders \(N_1,\dots, N_d\)\, and \(h=g_1^{a_1}\dots g_d^{a_d}\),\, with \(a_i\in [0,N_i]\),\, how to find the exponents \(a_i\).\par For \(d=1\)\, this is the classical DLP, widely used in Public-key Cryptography. One way to solve this problem it is the called tame and wild kangaroo method of \textit{J. M. Pollard} [Math. Comput. 32, 918--924 (1978; Zbl 0382.10001)]. For the multidimensional case \textit{P. Gaudry} and \textit{É. Schost} [Lect. Notes Comput. Sci. 3076, 208--222 (2004; Zbl 1125.11360)] gave a similar low-memory algorithm based on tame and wild walks.\par Several improvements to the Gaudry-Schost have been proposed in the literature. \textit{S. D. Galbraith} and \textit{R. S. Ruprai} [Lect. Notes Comput. Sci. 6056, 368--383 (2010; Zbl 1270.11124)] gave an algorithm.with an specific overlap of tame and wild regions.\par The first variant of the present paper follows the paths of the Galbraith-Ruprai algorithm. This variant is discusses in Section 3 and the comparison of the expected time complexity for this variant and the Gaudry-Schost and Galbraith-Ruprai algorithms is provided in Table 1.\par Section 4 deals with the second proposed variant which fixes the tame region and it adjusts the size of the wild one. Table 2 shows the comparison of the expected tome complexity of this second variant and the complexity of the Gaudry-Schost and Galbraith-Ruprai algorithms.