


DOI: 10.17587/it.28.2632 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 RoMethod for Finding a Discrete Logarithm in the Case of its Low Weight In this paper, we present a modification of Pollard's romethod 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 BerryEsseen theorem for the Bernoulli scheme. 