Abstract:
Discrete logarithm problem in a finite group $G$ with the efficient inversion consists in solving the equation $Q=nP$ with respect to $n$ in the interval $(-N/2,N/2)$ for the specified $P,Q\in G$, $0<N<|G|-1$. If the inversion in the group $G$ may be computed significantly faster than the group operation, then analogously to the solution of the classical discrete logarithm, we may speed up the algorithm. In 2010, S. Galbraith and R. Ruprai proposed an algorithm solving this problem with the average complexity $(1{,}36+\mathrm o(1))\sqrt N$ of group operations in $G$ where $N\to\infty$. We show that the average complexity of the algorithm for finding the solution of the discrete logarithm problem in the interval $(-N/2,N/2)$ equals $(1+\varepsilon)\sqrt{\pi N/2}$ group operations.
Keywords:discrete logarithm problem in interval, Gaudry–Schost algorithm.
Fulltext:
PDF file (547 kB)