Math/Algebra
-
The Discrete Logarithm Problem
The discrete logarithm problem (DLP) is a fundamental problem in group theory that underpins the security of many cryptographic systems, including elliptic curve cryptography and the Diffie-Hellman key exchange.
In a cyclic group $G$ with generator $g$, every element $h\in G$ can be expressed as $h=g^x$ for some integer $x$. Computing $g^x$ given $g$ and $x$ is fast and efficient – $\mathcal O(\log x)$ using the method of repeated squaring.
The inverse problem, however – given $g$ and $h=g^x$, find $x$ – is believed to be computationally hard in certain groups. We haven’t proven that it’s hard (P vs NP is still an open problem), but we have decades of cryptanalysis and no known efficient algorithms for solving DLP in well-chosen groups, which gives us confidence in its hardness.