We will see that such an answer does not always exists and describe an algorithm that gives an answer provided it exists. In the video in Figure 15.28 we give an overview of this section. Details and more examples can be found below.
Example15.29.Powers in \((\Z_7^\otimes,\otimes)\).
In \((\Z_7^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 7\) we investigate the powers of all elements. Recall that \(\Z_7^\otimes=\{1,2,3,4,5,6\}\) and \(\W=\{0,1,2,\dots\}\text{.}\)
powers of \(1\text{:}\).
\(\gexp{1}{0}{\otimes}=1\text{,}\)\(\gexp{1}{1}{\otimes}=1\text{,}\)\(\gexp{1}{2}{\otimes}=1\text{;}\) as we obtain the \(n\)-th power of \(1\) multiplying \(n\) copies of \(1\) we have for all \(n\in\W\) that \(\gexp{1}{n}{\otimes}=1\text{.}\)
\(\gexp{2}{0}{\otimes}=1\text{,}\)\(\gexp{2}{1}{\otimes}=2\text{,}\)\(\gexp{2}{2}{\otimes}=4\text{,}\)\(\gexp{2}{3}{\otimes}=1\text{,}\)\(\gexp{2}{4}{\otimes}=2\text{;}\) when we continue multiplying by 2 we cycle through 1, 2, and 4, see Figure 15.30 (b).
\(\gexp{3}{0}{\otimes}=1\text{,}\)\(\gexp{3}{1}{\otimes}=3\text{,}\)\(\gexp{3}{2}{\otimes}=2\text{,}\)\(\gexp{3}{3}{\otimes}=6\text{,}\)\(\gexp{3}{4}{\otimes}=4\text{,}\)\(\gexp{3}{5}{\otimes}=5\text{,}\)\(\gexp{3}{6}{\otimes}=1\text{;}\) so all elements of \(\Z_7^\otimes\) are powers of 3, see Figure 15.30 (c).
\(\gexp{4}{0}{\otimes}=1\text{,}\)\(\gexp{4}{1}{\otimes}=4\text{,}\)\(\gexp{4}{2}{\otimes}=2\text{,}\)\(\gexp{4}{3}{\otimes}=1\text{,}\)\(\gexp{4}{4}{\otimes}=4\text{;}\) when we continue multiplying by 4 we cycle through 1, 4, and 2.
\(\gexp{5}{0}{\otimes}=1\text{,}\)\(\gexp{5}{1}{\otimes}=5\text{,}\)\(\gexp{5}{2}{\otimes}=4\text{,}\)\(\gexp{5}{3}{\otimes}=6\text{,}\)\(\gexp{5}{4}{\otimes}=2\text{,}\)\(\gexp{5}{5}{\otimes}=4\text{,}\)\(\gexp{5}{6}{\otimes}=1\text{;}\) so all elements of \(\Z_7^\otimes\) are powers of 5.
Let \((G,\star)\) be a group. For two \(a\) and \(b\) in \(G\) the discrete logarithm of \(a\) to base \(b\) is the answer to the following question. For which \(n\in\W\) do we have:
Example15.31.There is no \(n\) with \(\gexp{2}{n}{\otimes}=3\) in \((\Z_7^\otimes,\otimes)\).
In \((\Z_7^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 7\) there is no \(n\in\W\) such that \(\gexp{2}{n}{\otimes}=3\text{,}\) because the only powers of 2 in \((\Z_7^\otimes,\otimes)\) are \(1\text{,}\)\(2\text{,}\) and \(4\) (compare Example 15.29powers of \(2\)).
Let \((G,\star)\) be a group and let \(b\in G\) and \(a\in G\text{.}\) The discrete logarithm of \(a\) to base \(b\) with respect to \(\star\) is the the smallest non-negative integer \(n\) such that \(\gexp{b}{n}{\star}=a\text{.}\) If such an \(n\) does not exist we say that the discrete logarithm does not exist.
Specializing Definition 15.32 to the group \((\Z_p^\otimes,\otimes)\) we have for all \(b\in\Z_p^\otimes\) and \(a\in\Z_p^\otimes\) that \(\glog{b}{a}{\otimes}\) is the smallest non-negative integer such that \(\gexp{b}{n}{\otimes}=a\text{.}\)
To find discrete logarithms we often have two try out several possible answers. Sometimes we cannot find an answer and we conclude that the discrete logarithm does not exist.
Continuing this we get \(\gexp{4}{4}{\otimes}=1\text{,}\)\(\gexp{4}{5}{\otimes}=4\text{,}\)\(\gexp{4}{6}{\otimes}=1\text{.}\) As \(4\otimes 4=1\) and \(1\otimes 4=4\) further multiplication by \(4\) only yields 1 or 4. So the only numbers that can be written as powers of \(4\) in \((\Z_5^\otimes)\) are \(1\) and \(4\text{.}\) This means that there is no non-negative integer \(n\) such that \(\gexp{4}{n}{\otimes}=2\text{.}\) We have found that \(\glog{4}{2}{\otimes}\) does not exist.
Example15.36.All elements of \(\Z_7^\otimes\) are powers of \(5\).
We give powers of elements and the corresponding discrete logarithm to base 5 for the elements of the group \((\Z_7^\otimes,\otimes)\) where \(a\otimes b =(a\cdot b)\fmod 7\text{.}\) We see that all elements of \(\Z_7^\otimes\) can be written as powers of \(5\text{.}\)
We have \(\gexp{5}{0}{\otimes}=1\text{.}\) Thus \(\glog{5}{1}{\otimes}=0\text{.}\)
Example15.37.Powers and logarithm functions are each others inverses.
In the group \((\Z_5^\otimes,\otimes)\) where \(a\otimes b =(a\cdot b)\fmod 5\) we consider exponentiation and logarithm with base \(3\text{.}\) Let the function \(e:\Z_4\to \Z_5^\otimes\) be given by \(e(x)=\gexp{3}{x}{\otimes}\text{.}\) The function \(e\) is the exponentiation function with base \(3\text{.}\) We have
The discrete logarithm \(\glog{3}{y}{\otimes}\) of \(y\in\Z_5^\otimes\) to base \(3\) is the the smallest non-negative integer \(n\) such that \(\gexp{3}{n}{\otimes}=y\text{.}\) Let the function given by \(l:\Z_5^\otimes\to\Z_4\) be given by
Depending on the group, the effort of finding discrete logarithms varies considerably. Different approaches can be used to find discrete logarithms. For small groups, we can produce a table where we can quickly look up the values.
We need to find \(n\in\W\) such that \(\gexp{3}{n}{\otimes}=6\text{.}\) From Figure 15.30(c) we see that \(\gexp{3}{3}{\otimes}=3\otimes 3\otimes 3=6\text{.}\) Thus \(\glog{3}{6}{\otimes}=3\text{.}\)
In general we try out exponents until we find the right one. We never have to try out more exponents than our group has elements, so we know when to stop in case the discrete logarithm does not exist.
The method that we applied to find the discrete logarithm is called the naive method. We formulate it as an algorithm. To assure that our algorithm terminates we assume that our group is finite. When the group of is finite, the number of possible distinct powers of any element of the group is at most the number of elements in the group. We make this the termination criterion for the loop in our algorithm.
A non-negative integer \(n\) such that \(\gexp{b}{n}{\star}=a\) if such an \(n\) exits, “the discrete logarithm to base \(b\) of \(a\) does not exist” otherwise.
Next we illustrate with an example that computing powers using fast exponentiation is considerably faster than finding discrete logarithms with the naive method.
Problem15.41.Complexity of computing \(\glog{2}{5}{\otimes}\).
In the group \((\Z_{101}^\otimes,\otimes)\) where \(\otimes:\Z_{101}^\otimes\times\Z_{101}^\otimes\to\Z^\otimes_{101}\) is defined by \(a\otimes b=(a\cdot b)\fmod 101\text{.}\)
The previous problem illustrates that more group operations are needed to find the discrete logarithm than for computing the corresponding power with the fast exponentiation algorithm (Algorithm 15.22). In Problem 15.26, we computed \(\gexp{2}{28}{\otimes}\) in 5 group operations \(\otimes\) while it took \(23\) group operations \(\otimes\) to find \(\glog{2}{5}{\otimes}\text{.}\) In general, computing discrete logarithms in the group \((\Z_p^\otimes,\otimes)\) is difficult.
There are methods for computing discrete logarithms in the group \((\Z_p^\otimes,\otimes)\) that are faster than checking all powers of the generator. Some of the methods are the Baby Step Giant Step algorithm, index calculus algorithm, and the number field sieve, all of which are outside the scope of this course.
Since the discrete logarithm is much harder to compute than exponentiation, in the next section we will present two public key crypto systems whose security depends on the fact that powers are faster to compute than discrete logarithms.
