Introduction to Cryptography with Coding Theory, 3rd Edition

Chapter 10 Discrete Logarithms

10.1 Discrete Logarithms

In the RSA algorithm, we saw how the difficulty of factoring yields useful cryptosystems. There is another number theory problem, namely discrete logarithms, that has similar applications.

Fix a prime $p$. Let $\alpha$ and $\beta$ be nonzero integers mod $p$ and suppose

$$\begin{array}{cc}\beta \equiv {\alpha }^x& (\text{mod }p)\end{array}$$

The problem of finding $x$ is called the discrete logarithm problem. If $n$ is the smallest positive integer such that $\begin{array}{cc}{\alpha }^n\equiv 1& (\text{mod}p)\end{array}$, we may assume $0\le x<n$, and then we denote

$$x=L_{\alpha }(\beta )$$

and call it the discrete log of $\beta$ with respect to $\alpha$ (the prime $p$ is omitted from the notation).

For example, let $p=11$ and let $\alpha =2$. Since $2^6\equiv 9(\text{mod}11)$, we have $L_2(9)=6$. Of course, $2^6\equiv 2^{16}\equiv 2^{26}\equiv 9(\text{mod}11)$, so we could consider taking any one of 6, 16, 26 as ...