An Overview of the Discrete Logarithm Problem in Cryptography

The discrete logarithm problem is a computationally hard problem that is widely employed in public-key cryptography, based on the assumption that there exists no general method to efficiently solve discrete logs. In this paper, we investigate the historical evolution, theoretical foundations, associated equations, implementation techniques, applications, and security aspects of the discrete logarithm problem. A timeline detailing the early development of discrete logarithms in cryptography is presented. The algorithms deployed to solve discrete logarithm problems, including Shanks’ baby step–giant step algorithm, Pohling–Hellman’s algorithm, Pollard’s Rho algorithm, Pollard’s Kangaroo algorithm, index calculus, and function field sieve, are discussed. Additionally, an overview of Shor’s quantum algorithms is provided. The paper also offers concise discussions of schemes such as Diffie–Hellman key exchange, ElGamal encryption, and elliptic curve cryptography.