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  to be a primitive root mod , so  is the smallest positive exponent  such that . This implies that



Assume that



We want to find .

First, it’s easy to determine . Note that



so  (see Exercise 15 in Chapter 3). However,  is assumed to be the smallest exponent to yield , so we must have



Starting with , raise both sides to the  power to obtain



Therefore, if , then  is even; otherwise,  is odd.

Example

Suppose we want to solve . Since



we must have  even. In fact, , 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  has only small prime factors. Suppose



is the factorization of  into primes. Let  be one of the factors. We’ll compute . If this can be done for each , the answers can be recombined using the Chinese remainder theorem to find the discrete logarithm.

Write



We’ll determine the coefficients  successively, and thus obtain . Note that



where  is an integer. Starting with , raise both sides to the  power to obtain



The last congruence is a consequence of Fermat’s theorem: . To find , simply look at the powers



until one of them yields . Then . Note that since , and since the exponents  are distinct mod , there is a unique  that yields the answer.

An extension of this idea yields the remaining coefficients. Assume that . Let



Raise both sides to the  power to obtain



The last congruence follows by applying Fermat’s theorem. We couldn’t calculate  as  since fractional exponents cause problems. Note that every exponent we have used is an integer.

To find , simply look at the powers



until one of them yields . Then .

If , let  and raise both sides to the  power to obtain . In this way, we can continue until we find that  doesn’t divide . Since we cannot use fractional exponents, we must stop. But we have determined , so we know .

Repeat the procedure for all the prime factors of . This yields  mod  for all . The Chinese remainder theorem allows us to combine these into a congruence for  mod . Since , this determines .

Example

Let , , and . We want to solve



Note that



First, let  and let’s find . Write .

To start,



and



Since



we have . Next,



Also,



Since



we have . Continuing, we have



and



Therefore, . We have obtained



Now, let  and let’s find  mod 5. We have



and



Trying the possible values of  yields



Therefore,  gives the desired answer, so .

Since  and , we combine these to obtain , so . A quick calculation checks that , as desired.

As long as the primes  involved in the preceding algorithm are reasonably small, the calculations can be done quickly. However, when  is large, calculating the numbers  for  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  has a large prime factor.

Note that even if  has a large prime factor , the algorithm can determine discrete logs mod  if  is composed of small prime factors. For this reason, often  is chosen to be a power of . Then the discrete log is automatically 0 mod , so the discrete log hides only mod  information, which the algorithm cannot find. If the discrete log  represents a secret (or better,  times a secret), this means that an attacker does not obtain partial information by determining  mod , 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  such that . She does the following. First, she chooses an integer  with , for example  (where  means round  up to the nearest integer). Then she makes two lists:

1.  for 

2.  for 

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



so . Therefore,  solves the discrete log problem.

Why should there be a match? Since , we can write  in base  as  with . In fact,  and . Therefore,



gives the desired match.

The list  for  is the set of “Baby Steps” since the elements of the list are obtained by multiplying by , while the “Giant Steps” are obtained in the second list by multiplying by . 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  and it requires storing approximately  numbers. Therefore, the method works for primes  up to , or even slightly larger, but is impractical for very large .

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 , where  is a large prime and  is a primitive root.

First, there is a precomputation step. Let  be a bound and let  be the primes less than . This set of primes is called our factor base. Compute  for several values of . For each such number, try to write it as a product of the primes less than . If this is not the case, discard . However, if , then



When we obtain enough such relations, we can solve for  for each .

Now, for random integers , compute . For each such number, try to write it as a product of primes less than . If we succeed, we have , which means



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

Example

Let  and . Let , so we are working with the primes 2,3,5,7. A calculation yields the following:



Therefore,



The second congruence yields . Substituting this into the third congruence yields . The fourth congruence yields only the value of  since . This gives two choices for . Of course, we could try them and see which works. Or we could use the fifth congruence to obtain . This finishes the precomputation step.

Suppose now that we want to find . Trying a few randomly chosen exponents yields , so



Therefore, .

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

10.2.4 Computing Discrete Logs Mod 4

When , the Pohlig-Hellman algorithm computes discrete logs mod 4 quite quickly. What happens when ? The Pohlig-Hellman algorithm won’t work, since it would require us to raise numbers to the  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 , then we can use it to compute discrete logs mod  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 . Therefore, we should be able to obtain information on the discrete log only modulo the power of 2 that appears in . When , 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 . For example, . We defined  to be 6 in this case; if we had allowed it also to be 16, we would have two values for , namely 6 and 16, that are not congruent mod 4. Therefore, from this point of view, we shouldn’t even be asking about .

We need the following lemma, which is similar to the method for computing square roots mod a prime  (see Section 3.9).

Lemma

Let  be prime, let , and let  be an integer. Suppose  and  are two nonzero numbers mod  such that . Then



Proof.



The final congruence is because of Fermat’s theorem.

Fix the prime  and let  be a primitive root. Assume we have a machine that, given an input , gives the output . As we saw previously, it is easy to compute . So the new information supplied by the machine is really only the second bit of the discrete log.

Now assume . Let  be the binary expansion of . Using the  machine, we determine  and . Suppose we have determined  with . Let



Using the lemma  times, we find



Applying the  machine to this equation yields the value of . Proceeding inductively, we obtain all the values . This determines , 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  is hard, then so is computing such discrete logs mod 4.