TAOCP 4.5.4 Exercise 46
Let $p$ be a prime, let $a$ be a primitive root modulo $p$, and let b \equiv a^n \pmod p, \qquad 0\le n\le p-2.
Section 4.5.4: Factoring into Primes
Exercise 46. [HM30] (L. Adleman.) Let $p$ be a rather large prime number and let $a$ be a primitive root modulo $p$; thus, all integers $b$ in the range $1 \le b < p$ can be written $b = a^n \bmod p$, for some unique $n$ with $1 \le n \le p$.
Design an algorithm that almost always finds $n$, given $b$, in $O(p^\epsilon)$ steps for all $\epsilon > 0$, using ideas similar to those of Dixon's factoring algorithm. [Hint: Start by building a repertoire of numbers $n_i$ such that $a^{n_i} \bmod p$ has only small prime factors.]
Verified: yes
Solve time: 2m23s
Setup
Let $p$ be a prime, let $a$ be a primitive root modulo $p$, and let
$$ b \equiv a^n \pmod p, \qquad 0\le n\le p-2. $$
The problem is to determine $n$, given $a$, $b$, and $p$.
The exercise asks for an algorithm analogous to Dixon's factoring method. The essential idea is to collect many multiplicative relations involving numbers whose prime factors are all small, then solve a linear system modulo $p-1$, because
$$ a^x a^y \equiv a^{x+y}\pmod p. $$
Let
$$ B={q_1,q_2,\ldots,q_t} $$
be the factor base consisting of all primes not exceeding a bound $y$. We shall choose $y$ so that
$$ t=\pi(y)=p^{o(1)}. $$
The goal of the first stage is to determine the discrete logarithms
$$ L_i=\log_a q_i \pmod{p-1} \qquad (1\le i\le t). $$
After these values are known, the logarithm of an arbitrary element can be obtained from one additional smooth relation.
Solution
Choose random integers $r$ with $0\le r\le p-2$ and compute
$$ A_r=a^r\bmod p. $$
Whenever $A_r$ factors completely over the factor base,
$$ A_r=\prod_{i=1}^{t} q_i^{e_i}, $$
we obtain the congruence
$$ r \equiv \sum_{i=1}^{t} e_iL_i \pmod{p-1}. \tag{1} $$
Each such smooth value therefore yields one linear equation in the unknowns
$L_1,\ldots,L_t$.
Continue generating random exponents until at least $t+c$ independent equations have been obtained, where $c$ is a fixed positive constant. Solving the resulting linear system modulo $p-1$ determines all $L_i$.
To justify this step, observe that (1) is a linear relation over the ring
$\mathbf Z/(p-1)\mathbf Z$. The coefficient vectors $(e_1,\ldots,e_t)$ behave essentially randomly. After collecting more than $t$ independent relations, Gaussian elimination modulo each prime-power divisor of $p-1$ determines the unique solution for the $L_i$, and the Chinese remainder theorem combines the results.
Having computed the logarithms of the factor-base primes, determine $\log_a b$ as follows.
Choose random integers $s$ and compute
$$ C_s=b,a^s \bmod p. $$
Whenever $C_s$ is $B$-smooth,
$$ C_s=\prod_{i=1}^{t} q_i^{f_i}, $$
we have
$$ b,a^s \equiv a^{\sum_i f_iL_i} \pmod p. $$
Hence
$$ n+s \equiv \sum_{i=1}^{t} f_iL_i \pmod{p-1}, $$
and therefore
$$ n \equiv \sum_{i=1}^{t} f_iL_i-s \pmod{p-1}. \tag{2} $$
Equation (2) yields the desired discrete logarithm.
The remaining question is the running time.
Let
$$ y=\exp!\bigl(\sqrt{\log p,\log\log p}\bigr). $$
Then
$$ t=\pi(y) = \exp!\bigl((1+o(1)) \sqrt{\log p,\log\log p}\bigr), $$
by equation (4) of the text.
A standard estimate for smooth numbers shows that a random integer below $p$ is $y$-smooth with probability
$$ \exp!\bigl(-(1+o(1)) \sqrt{\log p,\log\log p}\bigr). $$
Therefore the expected number of trials needed to obtain one relation is
$$ \exp!\bigl((1+o(1)) \sqrt{\log p,\log\log p}\bigr). $$
Since only $t+O(1)$ relations are required, the total expected work is
$$ \exp!\bigl((2+o(1)) \sqrt{\log p,\log\log p}\bigr). \tag{3} $$
For every fixed $\epsilon>0$,
$$ \exp!\bigl((2+o(1)) \sqrt{\log p,\log\log p}\bigr) = o(p^\epsilon), $$
because
$$ \frac{\sqrt{\log p,\log\log p}}{\log p} \to0. $$
Thus the algorithm requires $O(p^\epsilon)$ steps for every $\epsilon>0$.
Verification
For each relation
$$ a^r \equiv \prod q_i^{e_i}\pmod p, $$
taking discrete logarithms base $a$ gives
$$ r\equiv \sum e_iL_i \pmod{p-1}, $$
because $a$ is a primitive root and the exponent group modulo $p$ has order $p-1$.
After solving for the $L_i$, a relation
$$ b,a^s \equiv \prod q_i^{f_i}\pmod p $$
implies
$$ a^{n+s} \equiv a^{\sum f_iL_i} \pmod p. $$
Since exponents are unique modulo $p-1$,
$$ n+s\equiv \sum f_iL_i\pmod{p-1}, $$
which yields (2). Therefore the algorithm returns the unique discrete logarithm of $b$.
The complexity estimate (3) is subexponential in $\log p$ and satisfies
$$ \exp!\bigl((2+o(1)) \sqrt{\log p,\log\log p}\bigr) = O(p^\epsilon) $$
for every fixed $\epsilon>0$.
Notes
This method is the discrete-logarithm analogue of Dixon's factoring algorithm. The factor base plays the same role in both algorithms: random values are generated until enough of them factor completely over a small set of primes, producing linear relations. In the factoring problem the relations yield dependencies among exponent vectors; here they determine the unknown logarithms of the factor-base primes, after which any target logarithm is obtained from one additional smooth relation.
$$ \boxed{\text{Expected running time } \exp!\bigl((2+o(1)) \sqrt{\log p,\log\log p}\bigr) =O(p^\epsilon)\text{ for every }\epsilon>0.} $$