Алгоритм baby-step giant-step як інструмент обчислення дискретного логарифма в теорії чисел та вищій математиці

Abstract

The discrete logarithm problem is one of the fundamental mathematical challenges upon which the security of modern asymmetric cryptographic systems is built, including the Diffie-Hellman key exchange protocol, the ElGamal cryptosystem, and elliptic curve cryptography. Its mathematical essence lies in finding an unknown exponent in the equation g^x≡h (mod p), where g (the base), h (the result), and p (the modulus) are known integers. To solve this problem, the classical brute-force method is extremely inefficient and practically impossible for large values of the modulus p. The "baby-step giant-step" algorithm (also known as Shanks's algorithm), proposed by Daniel Shanks in 1971, allows for significant optimization of this process. This method is based on the "meet-in-the-middle" paradigm and allows for a reduction in computational search complexity from O(p) to O(√p)while requiring O(√p) memory to store intermediate results. This paper examines a software implementation of Shanks's algorithm using the Python programming language. The choice of this language is driven by its high-level architecture, support for arbitrary-precision integers (which is critical for cryptography), and the availability of efficient built-in data structures. In particular, the use of dictionaries (hash tables) ensures an instantaneous search for collisions between two calculated sets of values - the "baby steps" and "giant steps." The developed implementation serves not only as a visual tool for the in-depth study of the mathematical foundations of cryptanalysis but also demonstrates the practical vulnerability of certain cryptosystem parameters, which is an important stage in the training of information security specialists.