Geodesic
On the complexity of discrete logarithm problem in a finite cyclic group with the efficient inversion
Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 149-151 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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$. 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. 
@article{PDMA_2015_8_a57,
     author = {M. V. Nikolaev},
     title = {On the complexity of discrete logarithm problem in a~finite cyclic group with the efficient inversion},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {149--151},
     year = {2015},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2015_8_a57/}
}
TY  - JOUR
AU  - M. V. Nikolaev
TI  - On the complexity of discrete logarithm problem in a finite cyclic group with the efficient inversion
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2015
SP  - 149
EP  - 151
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/PDMA_2015_8_a57/
LA  - ru
ID  - PDMA_2015_8_a57
ER  - 
%0 Journal Article
%A M. V. Nikolaev
%T On the complexity of discrete logarithm problem in a finite cyclic group with the efficient inversion
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2015
%P 149-151
%N 8
%U http://geodesic.mathdoc.fr/item/PDMA_2015_8_a57/
%G ru
%F PDMA_2015_8_a57
M. V. Nikolaev. On the complexity of discrete logarithm problem in a finite cyclic group with the efficient inversion. Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 149-151. http://geodesic.mathdoc.fr/item/PDMA_2015_8_a57/

[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 | DOI | MR | Zbl

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

[4] 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

[5] Nikolaev M. N., “O slozhnosti zadachi diskretnogo logarifmirovaniya v intervale v gruppe s effektivnym invertirovaniem”, Prikladnaya diskretnaya matematika, 2015, no. 2(28), 97–102