# 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{}(\text{mod}\text{}p)$. This implies that

Assume that

We want to find $x$.

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

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

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

Therefore, if ${\beta}^{(p-1)/2}\equiv +1$, then $x$ is even; otherwise, $x$ is odd.

# Example

Suppose we want to solve ${2}^{x}\equiv 9\text{}(\text{mod}\text{}11)$. Since

we must have $x$ even. In fact, $x=6$, as we saw previously.

# 10.2.1 The Pohlig-Hellman Algorithm

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{}(\text{mod}\text{}{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{,}\text{}{x}_{1}\text{,}\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}\phantom{\rule{negativethinmathspace}{0ex}}\equiv \phantom{\rule{negativethinmathspace}{0ex}}\phantom{\rule{negativethinmathspace}{0ex}}1\text{}(\text{mod}\text{}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}}\phantom{\rule{thickmathspace}{0ex}}\u27fa\phantom{\rule{thickmathspace}{0ex}}{m}_{1}\equiv {m}_{2}\text{}(\text{mod}\text{}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{,}\text{}{x}_{1}\text{,}\text{}\dots \text{,}\text{}{x}_{r-1}$, so we know $x\text{}\text{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}{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$.

# Example

Let $p=41$, $\alpha =7$, and $\beta =12$. We want to solve

Note that

First, let $q=2$ and let’s find $x\text{}\text{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}{2}^{3}$. Write $x\equiv {x}_{0}+2{x}_{1}+4{x}_{2}\text{}(\text{mod}\text{}8)$.

To start,

and

Since

we have ${x}_{0}=1$. Next,

Also,

Since

we have ${x}_{1}=0$. Continuing, we have

and

Therefore, ${x}_{2}=1$. We have obtained

Now, let $q=5$ and let’s find $x$ mod 5. We have

and

Trying the possible values of $k$ yields

Therefore, ${37}^{3}$ gives the desired answer, so $x\equiv 3\text{}(\text{mod}\text{}5)$.

Since $x\equiv 5\text{}(\text{mod}\text{}8)$ and $x\equiv 3\text{}(\text{mod}\text{}5)$, we combine these to obtain $x\equiv 13\text{}(\text{mod}\text{}40)$, so $x=13$. A quick calculation checks that ${7}^{13}\equiv 12\text{}(\text{mod}\text{}41)$, as desired.

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{,}\text{}1\text{,}\text{}2\text{,}\text{}\dots \text{,}\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.

# 10.2.2 Baby Step, Giant Step

Eve wants to find $x$ such that ${\alpha}^{x}\equiv \beta \text{}(\text{mod}\text{}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:

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

$\beta {\alpha}^{-Nk}\text{}(\text{mod}\text{}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{,}\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{,}\text{}1\text{,}\text{}2\text{,}\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.

# 10.2.3 The Index Calculus

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{}(\text{mod}\text{}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{,}\text{}{p}_{2}\text{,}\text{}\dots \text{,}\text{}{p}_{m}\text{,}\text{}$ be the primes less than $B$. This set of primes is called our **factor base**. Compute ${\alpha}^{k}\text{}(\text{mod}\text{}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{}(\text{mod}\text{}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{}(\text{mod}\text{}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{}(\text{mod}\text{}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.

# Example

Let $p=131$ and $\alpha =2$. Let $B=10$, so we are working with the primes 2,3,5,7. A calculation yields the following:

Therefore,

The second congruence yields ${L}_{2}(5)\equiv 46\text{}(\text{mod}\text{}130)$. Substituting this into the third congruence yields ${L}_{2}(7)\equiv -34\equiv 96\text{}(\text{mod}\text{}130)$. The fourth congruence yields only the value of ${L}_{2}(3)\text{}(\text{mod}\text{}65)$ since $\text{gcd}\left(2\text{,}\text{}130\right)\text{}\overline{)\text{=}}\text{1}$. This gives two choices for ${L}_{2}(3)\text{}(\text{mod}\text{}130)$. Of course, we could try them and see which works. Or we could use the fifth congruence to obtain ${L}_{2}(3)\equiv 72\text{}(\text{mod}\text{}130)$. This finishes the precomputation step.

Suppose now that we want to find ${L}_{2}(37)$. Trying a few randomly chosen exponents yields $37\cdot {2}^{43}\equiv 3\cdot 5\cdot 7\text{}(\text{mod}\text{}131)$, so

Therefore, ${L}_{2}(37)=41$.

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

# 10.2.4 Computing Discrete Logs Mod 4

When $p\equiv 1\text{}(\text{mod}\text{}4)$, the Pohlig-Hellman algorithm computes discrete logs mod 4 quite quickly. What happens when $p\equiv 3\text{}(\text{mod}\text{}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{}(\text{mod}\text{}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{}(\text{mod}\text{}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{}(\text{mod}\text{}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{}\text{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}4$.

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

# Lemma

*Let $p\equiv 3\text{}(\text{mod}\text{}4)$ be prime, let $r\ge 2$, and let $y$ be an integer. Suppose $\alpha $ and $\gamma $ are two nonzero numbers mod $p$ such that $\gamma \equiv {\alpha}^{{2}^{r}y}\text{}(\text{mod}\text{}p)$. Then*

Proof.

The final congruence is because of Fermat’s theorem.

Fix the prime $p\equiv 3\text{}(\text{mod}\text{}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{}\text{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}4$. As we saw previously, it is easy to compute ${L}_{\alpha}(\beta )\text{}\text{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}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{}(\text{mod}\text{}p)$. Let $x={x}_{0}+2{x}_{1}+4{x}_{2}+\cdots +{2}^{n}{x}_{n}$ be the binary expansion of $x$. Using the ${L}_{\alpha}(\beta )\text{}(\text{mod}\text{}4)$ machine, we determine ${x}_{0}$ and ${x}_{1}$. Suppose we have determined ${x}_{0}\text{,}\text{}{x}_{1}\text{,}\text{}\dots \text{,}\text{}{x}_{r-1}$ with $r\ge 2$. Let

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

Applying the ${L}_{\alpha}\text{}(\text{mod}\text{}4)$ machine to this equation yields the value of ${x}_{r}$. Proceeding inductively, we obtain all the values ${x}_{0}\text{,}\text{}{x}_{1}\text{,}\text{}\dots \text{,}\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{}(\text{mod}\text{}4)$ is hard, then so is computing such discrete logs mod 4.