Discrete logarithm

In mathematics, for given real numbers a and b, the logarithm log_b a is a number x such that b^x = a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm log_b a is an integer k such that b^k = a. In arithmetic modulo an integer m, the more commonly used term is index: One can write k = ind_b a (mod m) (read "the index of a to the base b modulo m") for b^k ≡ a (mod m) if k is a primitive root of m and gcd(a,m) = 1.

Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general. In cryptography, the computational complexity of the discrete logarithm problem, along with its application, was first proposed in the Diffie–Hellman problem. Several important algorithms in public-key cryptography, such as ElGamal, base their security on the hardness assumption that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution.^[1]