Discrete logarithm

In mathematics, for given real numbers ${\displaystyle a}$ and ${\displaystyle b}$, the logarithm ${\displaystyle \log _{b}(a)}$ is a number ${\displaystyle x}$ such that ${\displaystyle b^{x}=a}$. The discrete logarithm generalizes this concept to a cyclic group. A simple example is the group of integers modulo a prime number (such as 5) under modular multiplication of nonzero elements.

For instance, take ${\displaystyle b=2}$ in the multiplicative group modulo 5, whose elements are ${\displaystyle {1,2,3,4}}$. Then: $${\displaystyle 2^{1}=2,\quad 2^{2}=4,\quad 2^{3}=8\equiv 3{\pmod {5}},\quad 2^{4}=16\equiv 1{\pmod {5}}.}$$ The powers of 2 modulo 5 cycle through all nonzero elements, so discrete logarithms exist and are given by: $${\displaystyle \log _{2}1=4,\quad \log _{2}2=1,\quad \log _{2}3=3,\quad \log _{2}4=2.}$$

More generally, in any group ${\displaystyle G}$, powers ${\displaystyle b^{k}}$ can be defined for all integers ${\displaystyle k}$, and the discrete logarithm ${\displaystyle \log _{b}(a)}$ is an integer ${\displaystyle k}$ such that ${\displaystyle b^{k}=a}$. In arithmetic modulo an integer ${\displaystyle m}$, the more commonly used term is index: One can write ${\displaystyle k=\mathbb {ind} _{b}a{\pmod {m}}}$ (read "the index of ${\displaystyle a}$ to the base ${\displaystyle b}$ modulo ${\displaystyle m}$") for ${\displaystyle b^{k}\equiv a{\pmod {m}}}$ if ${\displaystyle b}$ is a primitive root of ${\displaystyle m}$ and ${\displaystyle \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]