Discrete logarithm

A general logarithm is the inverse function of an exponential function, representing the power to which a fixed base must be raised to obtain a given number. That is, it refers to the value $x$ that satisfies $a^x=b$.

A discrete logarithm has the same form as a general logarithm but is defined in the discrete algebraic structure of group theory. The simplest form of a discrete logarithm is defined in $Z_p^{\ast }$. Let’s consider the set $Z_p^{\ast }=1,...,p-1$, which is closed under multiplication modulo a prime number $p$. Given an element $g$ and $y$ in $Z_p^{\ast }$, the discrete logarithm problem (DLP) is to find $x$ such that $g^x\equiv y\mathrm{mod}p$, i.e., to compute ${\log }_{g}y$.

When the prime $p$ is sufficiently large, it is easy to compute $y$ from $g$ and $x$, but it is difficult to find $x$ from $g$ and $y$. Cryptographic systems such as ElGamal and Diffie-Hellman exploit this property.