Skip to content
DSML.KZ
Publications

Article · Bulletin of the National Engineering Academy of the Republic of Kazakhstan · March 15, 2024

Investigation of the Silver–Pohlig–Hellman algorithm in discrete logarithm tasks

Institution ", Umut Turusbekova, M.A. Bersugir

Umut Turusbekova
Open via DOIPDFDOI 10.47533/2024.1606-146x.21

Abstract

This paper describes the formulation of the discrete logarithm problem, which is an important mathematical problem. The algorithm for calculating the Silver–Pohlig–Hellman discrete logarithm is analyzed and its disadvantages arising from the use of numbers of a special type called smooth are indicated. The problem that arises when searching for smooth primes of high bit depth is indicated. The process of searching for such numbers slows down the Silver–Pohlig Hellman algorithm, in addition, it is not known whether it is possible to find smooth primes of the required bit depth, because their number among the primes is extremely small, which calls into question the effectiveness of the algorithm. The concept of a smooth prime number is introduced, and a classification is proposed depending on the growth of consecutive multipliers into perfectly smooth and partially smooth primes. The first ten million primes were analyzed for smoothness, among which several tens were found to be perfectly smooth. It is shown that in order to search for smooth primes and analyze their properties, it is necessary to know how the primes are distributed depending on the number of prime factors. The results of the distribution of the first ten million primes are presented and assumptions about possible distribution laws are made. The problem of constructing a measure of smoothness is presented, which should be considered depending on the difference of adjacent factors and their degrees.

Cryptography and Residue ArithmeticAnalytic Number Theory ResearchCryptography and Data Securitydiscrete logarithm problemsmooth numbersinteger factorization

More by Umut Turusbekova