> [!NOTE] Definition (Discrete Logarithm Problem) > Given a [[Cyclic Group|cyclic group]] $G$, a generator $g$ for $G$ and some element $x$ of $G$, find $n$ such that $x=g^{n}$ (the [[Discrete Logarithm|discrete logarithm]] of $x$ base $g$). > > Or, given the [[Unit Group of Integers Modulo n|multiplicative group of integers modulo]] $p,$ $(Z/p\mathbb{Z})^{\times}$, where $p$ is a [[Prime numbers|prime]], a [[Primitive Root Modulo n|primitive root]] $a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ and some element $x \in (\mathbb{Z}/p\mathbb{Z})^{\times}$, find a number $n$ such that $x \equiv a^{n} \pmod{p}$ (the *discrete logarithm of* $x$ to the base $a$ modulo $n$). # Properties **Algorithms**: There is an efficient [[Shor's algorithm|quantum algorithm]] due to Peter Shor. It is conjectured that there is no polynomial time algorithm for solving solving DLP. # Applications **Cryptography**: If we solve DLP then we can easily solve [[Diffie-Hellman Problem|DHP]]. The [[Diffie-Hellman Key Exchange]] is based on the intractability of these problems.