The preceding idea was extended by Pohlig and Hellman to give an algorithm to compute discrete logs when $p-1$ has only small prime factors. Suppose

is the factorization of $p-1$ into primes. Let $q^r$ be one of the factors. We’ll compute $L_{\alpha }(\beta )(\text{mod}{q}^r)$. If this can be done for each $q_i^{r_i}$, the answers can be recombined using the Chinese remainder theorem to find the discrete logarithm.

Write

We’ll determine the coefficients $x_0\text{,}{x}_1\text{,}\dots x_{r-1}$ successively, and thus obtain $x\text{ mod }{q}^r$. Note that

where $n$ is an integer. Starting with $\beta \equiv {\alpha }^x$, raise both sides to the $(p-1)/q$ power to obtain

The last congruence is a consequence of Fermat’s theorem: ${\alpha }^{p-1}\equiv 1(\text{mod}p)$. To find $x_0$, simply look at the powers

until one of them yields ${\beta }^{(p-1)/q}$. Then $x_0=k$. Note that since ${\alpha }^{m_1}\equiv {\alpha }^{m_2}⟺m_1\equiv m_2(\text{mod}p-1)$, and since the exponents $k(p-1)/q$ are distinct mod $p-1$, there is a unique $k$ that yields the answer.

An extension of this idea yields the remaining coefficients. Assume that $q^2|p-1$. Let

Raise both sides to the $(p-1)/q^2$ power to obtain

The last congruence follows by applying Fermat’s theorem. We couldn’t calculate ${\beta }_1^{(p-1)/q^2}$ as $({\beta }_1^{p-1}{)}^{1/q^2}$ since fractional exponents cause problems. Note that every exponent we have used is an integer.

To find $x_1$, simply look at the powers

until one of them yields ${\beta }_1^{(p-1)/q^2}$. Then $x_1=k$.

If $q^3|p-1$, let ${\beta }_2\equiv {\beta }_1{\alpha }^{-x_{1}q}$ and raise both sides to the $(p-1)/q^3$ power to obtain $x_2$. In this way, we can continue until we find that $q^{r+1}$ doesn’t divide $p-1$. Since we cannot use fractional exponents, we must stop. But we have determined $x_0\text{,}{x}_1\text{,}\dots \text{,}{x}_{r-1}$, so we know $x\text{mod}{q}^r$.

Repeat the procedure for all the prime factors of $p-1$. This yields $x$ mod $q_i^{r_i}$ for all $i$. The Chinese remainder theorem allows us to combine these into a congruence for $x$ mod $p-1$. Since $0\le x<p-1$, this determines $x$.

As long as the primes $q$ involved in the preceding algorithm are reasonably small, the calculations can be done quickly. However, when $q$ is large, calculating the numbers ${\alpha }^{k(p-1)/q}$ for $k=0\text{,}1\text{,}2\text{,}\dots \text{,}q-1$ becomes infeasible, so the algorithm no longer is practical. This means that if we want a discrete logarithm to be hard, we should make sure that $p-1$ has a large prime factor.

Note that even if $p-1=tq$ has a large prime factor $q$, the algorithm can determine discrete logs mod $t$ if $t$ is composed of small prime factors. For this reason, often $\beta$ is chosen to be a power of ${\alpha }^t$. Then the discrete log is automatically 0 mod $t$, so the discrete log hides only mod $q$ information, which the algorithm cannot find. If the discrete log $x$ represents a secret (or better, $t$ times a secret), this means that an attacker does not obtain partial information by determining $x$ mod $t$, since there is no information hidden this way. This idea is used in the Digital Signature Algorithm, which we discuss in Chapter 13.

Eve wants to find $x$ such that ${\alpha }^x\equiv \beta (\text{mod}p)$. She does the following. First, she chooses an integer $N$ with $N^2\ge p-1$, for example $N=\lceil \sqrt{p-1}\rceil$ (where $\lceil x\rceil$ means round $x$ up to the nearest integer). Then she makes two lists:

1. ${\alpha }^j(\text{mod}p)$ for $0\le j<N$

2. $\beta {\alpha }^{-Nk}(\text{mod}p)$ for $0\le k<N$

She looks for a match between the two lists. If she finds one, then

so ${\alpha }^{j+Nk}\equiv \beta$. Therefore, $x=j+Nk$ solves the discrete log problem.

Why should there be a match? Since $0\le x<p-1\le N^2$, we can write $x$ in base $N$ as $x=x_0+N{x}_1$ with $0\le x_0\text{,}{x}_1<N$. In fact, $x_1=[x/N]$ and $x_0=x-N{x}_1$. Therefore,

gives the desired match.

The list ${\alpha }^j$ for $j=0\text{,}1\text{,}2\text{,}\dots$ is the set of “Baby Steps” since the elements of the list are obtained by multiplying by $\alpha$, while the “Giant Steps” are obtained in the second list by multiplying by ${\alpha }^{-N}$. It is, of course, not necessary to compute all of the second list. Each element, as it is computed, can be compared with the first list. As soon as a match is found, the computation stops.

The number of steps in this algorithm is proportional to $N\approx \sqrt{p}$ and it requires storing approximately $N$ numbers. Therefore, the method works for primes $p$ up to ${10}^{20}$, or even slightly larger, but is impractical for very large $p$.

For an example, see Example 35 in the Computer Appendices.

The idea is similar to the method of factoring in Subsection 9.4.1 . Again, we are trying to solve $\beta \equiv {\alpha }^x(\text{mod}p)$, where $p$ is a large prime and $\alpha$ is a primitive root.

First, there is a precomputation step. Let $B$ be a bound and let $p_1\text{,}{p}_2\text{,}\dots \text{,}{p}_m\text{,}$ be the primes less than $B$. This set of primes is called our factor base. Compute ${\alpha }^k(\text{mod}p)$ for several values of $k$. For each such number, try to write it as a product of the primes less than $B$. If this is not the case, discard ${\alpha }^k$. However, if ${\alpha }^k\equiv \prod p_i^{a_i}(\text{mod}p)$, then

When we obtain enough such relations, we can solve for $L_{\alpha }(p_i)$ for each $i$.

Now, for random integers $r$, compute $\beta {\alpha }^r(\text{mod}p)$. For each such number, try to write it as a product of primes less than $B$. If we succeed, we have $\beta {\alpha }^r\equiv \prod p_i^{b_i}(\text{mod}p)$, which means

This algorithm is effective if $p$ is of moderate size. This means that $p$ should be chosen to have at least 200 digits, maybe more, if the discrete log problem is to be hard.

Of course, once the precomputation has been done, it can be reused for computing several discrete logs for the same prime $p$.

When $p\equiv 1(\text{mod}4)$, the Pohlig-Hellman algorithm computes discrete logs mod 4 quite quickly. What happens when $p\equiv 3(\text{mod}4)$? The Pohlig-Hellman algorithm won’t work, since it would require us to raise numbers to the $(p-1)/4$ power, which would yield the ambiguity of a fractional exponent. The surprising fact is that if we have an algorithm that quickly computes discrete logs mod 4 for a prime $p\equiv 3(\text{mod}4)$, then we can use it to compute discrete logs mod $p$ quickly. Therefore, it is unlikely that such an algorithm exists.

There is a philosophical reason that we should not expect such an algorithm. A natural point of view is that the discrete log should be regarded as a number mod $p-1$. Therefore, we should be able to obtain information on the discrete log only modulo the power of 2 that appears in $p-1$. When $p\equiv 3(\text{mod}4)$, this means that asking questions about discrete logs mod 4 is somewhat unnatural. The question is possible only because we normalized the discrete log to be an integer between 0 and $p-2$. For example, $2^6\equiv 2^{16}\equiv 9(\text{mod}11)$. We defined $L_2(9)$ to be 6 in this case; if we had allowed it also to be 16, we would have two values for $L_2(9)$, namely 6 and 16, that are not congruent mod 4. Therefore, from this point of view, we shouldn’t even be asking about $L_2(9)\text{mod}4$.

We need the following lemma, which is similar to the method for computing square roots mod a prime $p\equiv 3(\text{mod}4)$ (see Section 3.9).

Fix the prime $p\equiv 3(\text{mod}4)$ and let $\alpha$ be a primitive root. Assume we have a machine that, given an input $\beta$, gives the output $L_{\alpha }(\beta )\text{mod}4$. As we saw previously, it is easy to compute $L_{\alpha }(\beta )\text{mod}2$. So the new information supplied by the machine is really only the second bit of the discrete log.

Now assume ${\alpha }^x\equiv \beta (\text{mod}p)$. Let $x=x_0+2x_1+4x_2+\cdots +2^n{x}_n$ be the binary expansion of $x$. Using the $L_{\alpha }(\beta )(\text{mod}4)$ machine, we determine $x_0$ and $x_1$. Suppose we have determined $x_0\text{,}{x}_1\text{,}\dots \text{,}{x}_{r-1}$ with $r\ge 2$. Let

Using the lemma $r-1$ times, we find

Applying the $L_{\alpha }(\text{mod}4)$ machine to this equation yields the value of $x_r$. Proceeding inductively, we obtain all the values $x_0\text{,}{x}_1\text{,}\dots \text{,}{x}_n$. This determines $x$, as desired.

It is possible to make this algorithm more efficient. See, for example, [Stinson1, page 175].

In conclusion, if we believe that finding discrete logs for $p\equiv 3(\text{mod}4)$ is hard, then so is computing such discrete logs mod 4.