A brief survey of the discrete logarithm problem

Abstract

The Discrete Logarithm Problem (DLP) has been the subject of interest among many mathematicians and cryptographers in recent times because of its computational di¢ culty. For the former, the enormity of the mathematics involved and the intellectual challenge that it entails are certainly motivating factors; for the latter, its usefulness in the ...eld of cryptography. Cryptosystems rest their security on some assumptions that certain mathematical problems are dificult to solve. The ElGamal cryptosystem, for instance, is considered secure because of the computational assumption that it is di¢ cult to solve the Discrete Logarithm Problem. The di¢ culty of the DLP lies in the fact that it has a “one-way” property. Its computational complexity is roughly measured by the computing time of the algorithm used to solve this mathematical problem. This paper is a brief survey of some of the best known algorithms for solving the DLP, examines their computing time, and considers the DLP over two particular ...nite groups.