Such an answer does not always exist. We describe an algorithm that gives an answer when it exists. The video in Figure 15.4.1 gives an overview of this section. Details and more examples follow.
Example15.4.2.Powers in \((\Z_7^\otimes,\otimes)\).
In \((\Z_7^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 7\) we study 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.4.3 (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.4.3 (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}=3\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.4.4.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.4.2powers 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\) for \(\star\) is 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.4.5 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 \(n\) 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.4.9.All elements of \(\Z_7^\otimes\) are powers of \(5\).
We give powers of elements and the matching 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.4.10.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{,}\) that is \(e(a)=\gexp{3}{a}{\otimes}\) We have:
The discrete logarithm \(\glog{3}{y}{\otimes}\) of \(y\in\Z_5^\otimes\) to base \(3\) is the smallest non-negative integer \(n\) such that \(\gexp{3}{n}{\otimes}=y\text{.}\) Let the function \(l:\Z_5^\otimes\to\Z_4\) be given by \(l(c)=\glog{3}{c}{\otimes}\text{.}\) We have:
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.4.3(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.
Problem15.4.14.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 uses more group operations to find the discrete logarithm than to compute the matching power with the fast exponentiation algorithm (Algorithm 15.3.5). In Problem 15.3.9, we computed \(\gexp{2}{24}{\otimes}\) in 5 group operations \(\otimes\text{.}\) It took \(23\) group operations \(\otimes\) to find \(\glog{2}{5}{\otimes}\text{.}\) In general, discrete logarithms are hard to compute in the group \((\Z_p^\otimes,\otimes)\text{.}\)
Some methods compute discrete logarithms in the group \((\Z_p^\otimes,\otimes)\) faster than checking every power of the generator. These methods include the Baby Step Giant Step algorithm, the index calculus algorithm, and the number field sieve. They are outside the scope of this course.
Computing a discrete logarithm is much harder than computing a power. In the next section, we present two public key crypto systems. Their security depends on powers being faster to compute than discrete logarithms.
