Geodesic
On the complexity of discrete logarithm problem in an interval in a~finite cyclic group with efficient inversion
Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 97-102.

Voir la notice de l'article provenant de la source Math-Net.Ru

Discrete logarithm problem in an interval in a finite group $G=\langle P\rangle$ consists in solving the equation $Q=nP$ with respect to $n\in\{-N/2,\dots,N/2\}$ for the specified $P,Q\in G$ and $0$. If the group $G$ has an inversion, which may be computed significantly faster than the group operation, then, similarly 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+\text o(1))\sqrt N$ 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 interval equals $(1+\varepsilon)\sqrt{\pi N/2}$ group operations.
Keywords: discrete logarithm problem in interval, Gaudry–Schost algorithm. 
@article{PDM_2015_2_a9,
     author = {M. V. Nikolaev},
     title = {On the complexity of discrete logarithm problem in an interval in a~finite cyclic group with efficient inversion},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {97--102},
     publisher = {mathdoc},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_2_a9/}
}
TY  - JOUR
AU  - M. V. Nikolaev
TI  - On the complexity of discrete logarithm problem in an interval in a~finite cyclic group with efficient inversion
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 97
EP  - 102
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_2_a9/
LA  - ru
ID  - PDM_2015_2_a9
ER  - 
%0 Journal Article
%A M. V. Nikolaev
%T On the complexity of discrete logarithm problem in an interval in a~finite cyclic group with efficient inversion
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 97-102
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_2_a9/
%G ru
%F PDM_2015_2_a9
M. V. Nikolaev. On the complexity of discrete logarithm problem in an interval in a~finite cyclic group with efficient inversion. Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 97-102. http://geodesic.mathdoc.fr/item/PDM_2015_2_a9/

[1] Gaudry P., Schost E., “A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm”, LNCS, 3076, 2004, 208–222 | MR | Zbl

[2] Galbraith S. D., Holmes M., “A non-uniform birthday problem with applications to discrete logarithms”, Discr. Appl. Math., 160:10–11 (2012), 1547–1560 ; http://eprint.iacr.org/2010/616 | MR | Zbl

[3] Gallant R., Lambert R., Vanstone S., “Faster point multiplication on elliptic curves with efficient endomorphisms”, CRYPTO'2001, LNCS, 2139, 2001, 190–200 | MR | Zbl

[4] Wiener M. J., Zuccherato R. J., “Faster attacks on elliptic curve cryptosystems”, LNCS, 1556, 1999, 190–200 | MR | Zbl

[5] Galbraith S. D., Ruprai R. S., “Using equivalence classes to accelerate solving the Discrete Logarithm Problem in a short interval”, LNCS, 6056, 2010, 368–383 ; http://eprint.iacr.org/2010/615 | MR | Zbl

[6] Liu W., Improved algorithms for the 2-dimensional discrete logarithm problem with equivalence classes, MSc Thesis, University of Auckland, 2010 http://www.math.auckland.ac.nz/~sgal018/Wei-Liu-MSc.pdf

[7] Nikolaev M. V., Matyukhin D. V., “On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with effective automorphism of order 6”, Discr. Math. Appl., 23:3–4 (2013), 313–325 | DOI | DOI | MR | Zbl