Section 3.2 Discrete logarithms
The core of mathematical cryptography is the existence of problems that are extremely hard to compute without an additional piece of information. One such problem takes advantage of the mixing effect of modular exponentiation in \(\F_p\ad\text{.}\)
Definition 3.2.1.
Let \(g\) be a generator for \(\F_p\) and let \(h\) be a nonzero element of \(\F_p\text{.}\) The Discrete Logarithm Problem (DLP) is the problem of finding an integer \(x\) so that
\begin{equation*}
g^x \equiv h \bmod p.
\end{equation*}
\(x\) is called the discrete logarithm base \(g\) of \(h\text{.}\) We use the notation of the classical logarithm and write \(\log_g(h) = x\text{.}\)Remark 3.2.2.
While we stated the discrete log problem for a generator \(g\text{,}\) (which has order \(p-1\)), we'll in practice need to use elements in \(\F_p\) with large prime order to avoid a clever attack called the Pohlig-Hellman algorithm, to be discussed later. The main point of the Pohlig-Hellman algorithm is that \(p-1\) is always composite when \(p\) is a large prime, and potentially can have lots of small factors (say a pile of \(2\)'s, for example). Thus, choosing an element with large prime order is necessary (though again, this makes the size of the spaces involved that much larger to compensate).Exercises Exercises
1.
\begin{equation*}
\log_g(hk) = \log_g(h) + \log_g(k)
\end{equation*}