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
We want to find .
First, it’s easy to determine . Note that
Starting with , raise both sides to the power to obtain
Therefore, if , then is even; otherwise, is odd.
Suppose we want to solve . Since
we must have even. In fact, , as we saw previously.
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.
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 .
Let , , and . We want to solve
First, let and let’s find . Write .
we have . Next,
we have . Continuing, we have
Therefore, . We have obtained
Now, let and let’s find mod 5. We have
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.
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:
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.
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.
Let and . Let , so we are working with the primes 2,3,5,7. A calculation yields the following:
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
Of course, once the precomputation has been done, it can be reused for computing several discrete logs for the same prime .
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).
Let be prime, let , and let be an integer. Suppose and are two nonzero numbers mod such that . Then
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.