TAOCP 5 Exercise 25

Section 5: Introduction to Sorting

Exercise 25. [M21] (Discrete logarithms.) You know that $p$ is a (rather large) prime number, and that $a$ is a primitive root modulo $p$. Therefore, for all $b$ in the range $1 \le b < p$, there is a unique $n$ such that $a^n \bmod p = b$, $1 \le n < p$. (This $n$ is called the index of $b$ modulo $p$, with respect to $a$.) Explain how to find $n$, given $b$, without needing $\Omega(n)$ steps. [Hint: Let $m = \lceil \sqrt{p} \rceil$ and try to solve $a^{mn_1} \equiv ba^{-n_2}$ (modulo $p$) for $0 \le n_1, n_2 < m$.]

Verified: yes
Solve time: 12m18s

Solution

Let $p$ be a prime and $a$ a primitive root modulo $p$. For a given $b$ with $1 \le b < p$ we must find the unique $n \in {1,2,\dots,p-1}$ such that [ a^n \equiv b \pmod{p}. ] The order of $a$ is $p-1$; therefore $n$ is determined modulo $p-1$ and the stated range gives the canonical representative.

Set $m = \lceil \sqrt{p} \rceil$. Because $n < p \le m^2$, we can write [ n = m n_1 + n_2 \qquad \text{with } 0 \le n_1, n_2 < m. ] This representation is unique. Substituting into the congruence gives [ a^{m n_1 + n_2} \equiv b \pmod{p} ;\Longleftrightarrow; a^{m n_1} \equiv b,a^{-n_2} \pmod{p}. ] Thus we must find a collision between the giant steps $a^{m n_1}$ ($0 \le n_1 < m$) and the baby steps $b,a^{-n_2}$ ($0 \le n_2 < m$).

Algorithm.

1. Compute $a^{-1} \bmod p$ (extended Euclidean algorithm, $O(\log p)$ steps).
2. Baby steps: Initialise $v = b$. For $n_2 = 0,1,\dots,m-1$ store the pair $(v, n_2)$ in a table $T$, then update $v \leftarrow v \cdot a^{-1} \bmod p$.
   (Thus the table contains the values $b,a^{-n_2} \bmod p$ for all $n_2$.)
3. Sort $T$ by the value $v$ (or insert into a hash table for $O(1)$ expected look‑up).
4. Giant steps: Compute $A = a^m \bmod p$ (by binary exponentiation). Initialise $u = 1$. For $n_1 = 0,1,\dots,m-1$ do:
   • Search $u$ in $T$. If a match $(u, n_2)$ is found, then $a^{m n_1} \equiv b,a^{-n_2} \pmod{p}$, hence
     [ n \equiv m n_1 + n_2 \pmod{p-1}. ] Reduce $m n_1 + n_2$ modulo $p-1$; if the result is $0$ output $p-1$, otherwise output the result.
   • Update $u \leftarrow u \cdot A \bmod p$.

Invariant. After $k$ iterations of the baby‑step loop, $v = b,a^{-k} \bmod p$. After $k$ iterations of the giant‑step loop, $u = a^{m k} \bmod p$.

Termination. Both loops run exactly $m$ times, so the algorithm always terminates.

Correctness. The true index $n$ satisfies $1 \le n \le p-1 < m^2$, so it has a unique representation $n = m n_1 + n_2$ with $0 \le n_1, n_2 < m$. For this pair, [ a^{m n_1} \equiv a^{n - n_2} \equiv b,a^{-n_2} \pmod{p}, ] hence the value $u = a^{m n_1}$ will appear in the table $T$ with the corresponding $n_2$. The algorithm finds this match and computes $n = m n_1 + n_2$. Reducing modulo $p-1$ yields the unique integer in ${1,\dots,p-1}$ congruent to the true index, which is exactly the desired $n$.

Complexity. The algorithm uses $O(m) = O(\sqrt{p})$ modular multiplications and $O(m)$ storage. The sorting (or hash table) adds $O(m \log m)$ or $O(m)$ expected time. This is $o(p)$ and therefore avoids $\Omega(n)$ steps (since $n$ can be as large as $p-1$).

This completes the proof. ∎