New Series of Rational Approximations and Some of Their Applications

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$.