ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 1. Vol. 28. 2022

DOI: 10.17587/it.28.26-32

M. A. Cherepnev, Ph. D., Professor, Lomonosov Moscow State University, Moscow, 119991, Moscow, Russian Federation, S. S. Gracheva, PhD, Associate Professor, National Research University Higher School of Economics, Moscow, 101000, Moscow, Russian Federation

Pollard's Ro-Method for Finding a Discrete Logarithm in the Case of its Low Weight

In this paper, we present a modification of Pollard's ro-method for searching for a discrete logarithm in the case when it is expressed by a binary vector of relatively small weight. In this case, it is necessary to change the procedure for iterating through random elements of the group under consideration in order to remain in the set of discrete logarithms expressed by binary vectors of low weight. We assume that this weight does not exceed half the length of the input word in the algorithm under consideration. To the other hand the case, when some close approximation of discrete logarithm is known considered. The paper uses estimates for binomial coefficients, the birthday paradox theorem, and the Berry-Esseen theorem for the Bernoulli scheme.
Keywords: Pollard's ro-method, birthday paradox theorem, Bernoulli scheme, parallel computing

To the contents