The Discrete Logarithm Problem
Learn about the discrete logarithm problem (DLP) and generalized discrete logarithm problem (GDLP) in this lesson.
The DLP in $\mathbb{F}_{p}^{*}$
As discussed in the previous sections, the first published publickey system by Diffie and Hellman is based on the discrete logarithm problem in the multiplicative group $\mathbb{F}_{p}^{*}$ of a finite field, with $p$ prime. According to the primitive root theorem
$F_{p}^{*}=\langle a\rangle=\left\{1, a, a^{2}, \ldots, a^{p2}\right\}.$
Discrete logarithm problem (DLP) in $\mathbb{F}_{p}^{*}$
Definition:
Let $a$ be a primitive element (i.e., a generator) of the cyclic group $\mathbb{F}_{p}^{*}$ and $b \in \mathbb{F}_{p}^{*}$. The DLP is the problem of finding an exponent $x$ such that
$a^{x} \equiv b \quad mod \space p$
$x$ is said to be the discrete logarithm of $b$ to the base $a$.
However, if there exists a solution for $x$, then there’s an infinite number of solutions to this problem. Due to Fermat’s little theorem
$a^{p1} \equiv 1 \quad mod \space p,$
and hence
$a^{x+k(p1)}=a^{x} \cdot\left(a^{p1}\right)^{k} \equiv b \cdot 1^{k} \equiv b \quad mod \space p.$
Thus, we conclude that if $x$ is a solution to the problem $a^{x} \equiv b \quad mod \space p$, then $x+k(p1)$ is also a solution for every $k \in \mathbb{Z}$.
Computing the DLP in $\mathbb{F}_{p}^{*}$ is a very hard computational problem if $p$ is sufficiently large. Since $a^{x} \equiv b \quad mod \space p$ can be computed efficiently if $x$ is known, this serves as a oneway function. However, there are several wellknown attacks against the DLP, which we introduce in this section.
The generalized discrete logarithm problem
So far, we just considered the DLP in the multiplicative group $\mathrm{F}_{p}^{*}$. However, the DLP isn’t restricted to only this group, but rather can generally be defined over any cyclic group.
Generalized DLP
Definition:
Let $G$ be a cyclic group with group operation *, a primitive element $a \in G$ and any given $b \in G$. Then, the discrete logarithm problem for $G$ is to find an integer $x$ that satisfies
$a^{x}=\{a * a * \ldots * a\}_{x \text { times }}=b .$
Every group $G$ has its own discrete logarithm problem, whereas the difficulty of the DLP depends on the structure of $G$. We consider the DLP for the following three cyclic groups: the additive group $\left(\mathbb{Z}_{n},+\right)$, the multiplicative group $\left(\mathbb{F}_{p}^{*}, \cdot\right)$, and the elliptic curve $\left(E\left(\mathbb{F}_{p}\right),+\right)$.

For $\left(\mathbb{Z}_{n},+\right)$, the DLP is to find an integer $x$ for two given $a, b \in \mathbb{Z}_{n}$ such that $x \cdot a=b \quad mod \space n$. This problem can be solved very easily since it works by using the Euclidean algorithm that takes $\mathcal{O}(\log (n))$ steps and hence works in polynomial time.

For $\left(\mathbb{F}_{p}^{*}, \cdot\right)$, the DLP is according to this definition. The solution is hard. For example, there exists the index calculus method that works in subexponential time. The bestknown algorithm is the generalized number field sieve, which also has a subexponential running time.

For $\left(E\left(F_{P}\right),+\right)$, the DLP (known as ECDLP) is to find an integer $x$ for two given points $P, Q \in\left(E\left(F_{p}\right),+\right)$ such that $x P=Q .$ However, the problem is very hard to solve since the fastest known algorithm takes $\mathcal{O}(\sqrt{p})$ steps and hence needs fully exponential time.
In conclusion, the ECDLP is harder than the DLP in $\left(\mathbb{F}_{P}^{*}, \cdot\right)$, provided that the orders of the groups are about the same.
Get handson with 1200+ tech skills courses.