> [!NOTE] Definition (Diffie-Hellman Problem) > Given a [[Cyclic Group|cyclic group]] $G$, a generator $g$ for $G$ and two elements $g^{a}, g^{b}$ of $G$, compute $g^{ab}$. > > Or, given $(Z/p\mathbb{Z})^{\times}$, where $p$ is a [[Prime numbers|prime]], a primitive root $a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ and $a^{x}, a^{y} \pmod{p}$ for $x,y \in \mathbb{Z}$, compute $a^{xy} \pmod{p}$. > [!Example] > Take $p=7$ and primitive root $g=5$. A DHP is given $g^a \equiv 4(\bmod 7)$ and $g^b \equiv 2(\bmod 7)$ what is $g^{a b}$ ? > >In this case we can use brute force to discover that $5^2 \equiv 4$ $(\bmod 7)$ and $5^4 \equiv 2(\bmod 7)$ so $g^{a b}=5^8=390625 \equiv 4(\bmod 7)$, but now think about doing this for a (much) larger prime $p$ and primitive root $g$. What condition on $g$ would be beneficial? > >Note, choosing $g^a \equiv 1(\bmod 7)$ would have been a bad choice because of Euler's Theorem. # Properties **Conjecture:** There is no polynomial time algorithm for solving solving the Diffie-Hellman Problem. # Applications **Cryptography**: If we solve [[Discrete Logarithm Problem (DLP)|DLP]] then we can easily solve DHP. The [[Diffie-Hellman Key Exchange]] is based on the intractability of these problems.