Geodesic
New Series of Rational Approximations and Some of Their Applications
Matematičeskie zametki, Tome 76 (2004) no. 2, pp. 237-257.

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

We consider the well-known discrete logarithm problem in a finite simple field $GF(p)$, where $p$ is a prime number, which has several application in problems of information protection. In Sec. 1, we introduce and study some number sequences arising in the continued fraction expansion of a real number. The results obtained are used in Sec. 2, where we introduce a new algorithm based on rational approximations for solving the problem of representing the discrete logarithm of a given number as the sum of logarithms of small primes; this problem is an important part of the discrete logarithm problem. We obtain several results necessary to construct and justify the representation algorithm. This algorithm is stated exactly in Sec. 3. We present several experimental results illustrating the work of the algorithm for prime numbers of the order of $10^16$–$10^31$. 
@article{MZM_2004_76_2_a7,
     author = {V. E. Tarakanov},
     title = {New {Series} of {Rational} {Approximations} and {Some} of {Their} {Applications}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {237--257},
     publisher = {mathdoc},
     volume = {76},
     number = {2},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2004_76_2_a7/}
}
TY  - JOUR
AU  - V. E. Tarakanov
TI  - New Series of Rational Approximations and Some of Their Applications
JO  - Matematičeskie zametki
PY  - 2004
SP  - 237
EP  - 257
VL  - 76
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2004_76_2_a7/
LA  - ru
ID  - MZM_2004_76_2_a7
ER  - 
%0 Journal Article
%A V. E. Tarakanov
%T New Series of Rational Approximations and Some of Their Applications
%J Matematičeskie zametki
%D 2004
%P 237-257
%V 76
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2004_76_2_a7/
%G ru
%F MZM_2004_76_2_a7
V. E. Tarakanov. New Series of Rational Approximations and Some of Their Applications. Matematičeskie zametki, Tome 76 (2004) no. 2, pp. 237-257. http://geodesic.mathdoc.fr/item/MZM_2004_76_2_a7/

[1] Borevich Z. I., Shafarevich I. R., Teoriya chisel, Nauka, M., 1964

[2] Khinchin A. Ya., Tsepnye drobi, ONTI NKTP, M., 1935

[3] Koblits N., Kurs teorii chisel i kriptografii, TVP, M., 2001

[4] Adleman L. M., “A subexponential algorithm for discrete logarithm problem with applications to cryptography”, Proc. of the 20th Annual IEEE Symposium on Foundations of Computer Science, 1979, 55–60

[5] Coppersmith D., Odlyzko A., Schroeppel R., “Discrete logarithms in $GF(p)$”, Algorithmica, 1 (1986), 1–15 | DOI | MR | Zbl

[6] Schirokauer O., “Discrete logarithms and local units”, Proc. Trans. Roy. Sci. London Ser. A, 345 (1993), 409–423 | DOI | MR | Zbl