Introduction to Cryptography with Coding Theory, 3rd Edition

10.2 Computing Discrete Logs

In this section, we present some methods for computing discrete logarithms. A method based on the birthday attack is discussed in Subsection 12.1.1.

For simplicity, take $\alpha$ to be a primitive root mod $p$, so $p-1$ is the smallest positive exponent $n$ such that ${\alpha }^n\equiv 1(\text{mod}p)$. This implies that

$${\alpha }^{m_1}\equiv \begin{array}{cc}{\alpha }^{m_2}& (\text{mod}p)\end{array}⟺m_1\equiv \begin{array}{cc}{m}_2& (\text{mod}p-1)\text{.}\end{array}$$

Assume that

$$\beta \equiv {\alpha }^x\text{,}0\le x<p-1.$$

We want to find $x$.

First, it’s easy to determine $x(\text{mod}2)$. Note that

$$({\alpha }^{(p-1)/2}{)}^2\equiv {\alpha }^{p-1}\equiv \begin{array}{cc}1& (\text{mod}p)\text{,}\end{array}$$

so ${\alpha }^{(p-1)/2}\equiv \pm 1(\text{mod}p)$ (see Exercise 15 in Chapter 3). However, $p-1$ is assumed to be the smallest exponent to yield $+1$, so we must have

$$\begin{array}{cc}{\alpha }^{(p-1)/2}\equiv -1& (\text{mod}p)\text{.}\end{array}$$

Starting with $\beta \equiv {\alpha }^x(\text{mod}p)$, raise both sides to the $(p-1)/2$ power to obtain

$$\begin{array}{cc}{\beta }^{(p-1)/2}\equiv {\alpha }^{x(p-1)/2}\equiv (-1{)}^x& (\text{mod}p)\text{.}\end{array}$$

Therefore, if ...