Discrete Logarithm

Section 15.4 Discrete Logarithm

The discrete logarithm to the base \(b\) of \(a\) is the answer to the question:

\(a\)\(b\text{,}\)\(m\)\(a=\gexp{b}{m}{\star}\)
🔗

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.4.1 we give an overview of this section. Details and more examples can be found below.

🔗

Figure 15.4.1. Discrete Logarithm by Matt Farmer and Stephen Steward

🔗

We investigate in a concrete example which elements of a group are powers of the group elements.

🔗

Example 15.4.2. 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{.}\)
🔗

🔗
powers of \(2\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).
🔗

🔗
powers of \(3\text{:}\).
\(\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).
🔗

🔗
powers of \(4\text{:}\).
\(\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.
🔗

🔗
powers of \(5\text{:}\).
\(\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.
🔗

🔗
powers of \(6\text{:}\).
\(\gexp{6}{0}{\otimes}=1\) and \(\gexp{6}{1}{\otimes}=6\text{;}\) all other powers of 6 are 1 or 6, see Figure 15.4.3 (a).
🔗

🔗

🔗

(a) The powers of 6, namely \(\gexp{6}{0}{\otimes}\!=1\) and \(\gexp{6}{1}{\otimes}\!=6\)
🔗

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:

\begin{equation*} \gexp{b}{n}{\star}=a \end{equation*}

Before we introduce a notation for the answer to this question, we look back at Example 15.4.2 and see that the answer does not always exist.

🔗

Example 15.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.2 powers of \(2\)).

🔗

Thus in our definition we have to allow for the possibility, that there is no answer.

🔗

Definition 15.4.5.

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.

🔗

We denote the discrete logarithm of \(a\) to base \(b\) with respect to \(\star\) by \(\glog{b}{a}{\star}\text{.}\)

🔗

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 such that \(\gexp{b}{n}{\otimes}=a\text{.}\)

🔗

We illustrate this in an example.

🔗

Example 15.4.6. Discrete logarithms in \((\Z_5^\otimes)\).

In the group \((\Z_5^\otimes)\) where \(a\otimes b:= (a\cdot b) \fmod 5\) we have:

\(\glog{2}{1}{\otimes}=0\) because \(\gexp{2}{0}{\otimes}=1\text{.}\)
🔗

🔗
\(\glog{2}{2}{\otimes}=1\) because \(\gexp{2}{1}{\otimes}=2\text{.}\)
🔗

🔗
\(\glog{2}{3}{\otimes}=3\) because \(\gexp{2}{3}{\otimes}=(2^3)\fmod 5=8\fmod 5=3\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.

🔗

Problem 15.4.7. Discrete logarithms in \((\Z_5^\otimes)\).

In the group \((\Z_5^\otimes)\) where \(a\otimes b:= (a\cdot b) \fmod 5\) find the following discrete logarithms provided they exits.

\(\displaystyle \glog{3}{2}{\otimes}\)
🔗

🔗
\(\displaystyle \glog{4}{2}{\otimes}\)
🔗

🔗

🔗

Solution.

We try out powers of \(3\) until we obtain 2.

\begin{align*} \gexp{3}{0}{\otimes}\amp =1\\ \gexp{3}{1}{\otimes}\amp =3\fmod 5 =3\\ \gexp{3}{2}{\otimes}\amp =3\otimes 3=(3\cdot 3)\fmod 5=9\fmod 5 = 4\\ \gexp{3}{3}{\otimes}\amp =\gexp{3}{2}{\otimes} \otimes 3=4\otimes 3=(4\cdot 3)\fmod 5= 12\fmod 5=2 \end{align*}

Thus \(\glog{3}{2}{\otimes}=3\text{.}\)

🔗

🔗
We try out powers of \(4\) until we obtain 2.

\begin{align*} \gexp{4}{0}{\otimes}\amp =1\\ \gexp{4}{1}{\otimes}\amp =4\fmod 5 =4\\ \gexp{4}{2}{\otimes}\amp =4\otimes 4=(4\cdot 4)\fmod 5=16\fmod 5 = 1\\ \gexp{4}{3}{\otimes}\amp =\gexp{4}{2}{\otimes} \otimes 4=(1\cdot 4)\fmod 5=4\fmod 5 = 4 \end{align*}

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.

🔗

🔗

🔗

The following follows from the definition of exponentiation and discrete logarithm.

🔗

Theorem 15.4.8.

Let \((G,\star)\) be a group and let \(a\in G\) and \(b\in G\text{.}\) We have

\(\glog{b}{1}{\star}=0\) because \(\gexp{b}{0}{\star}=1\text{.}\)
🔗

🔗
\(\glog{b}{b}{\star}=1\) because \(\gexp{b}{1}{\star}=b\text{.}\)
🔗

🔗

🔗

Example 15.4.9. 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{.}\)
🔗

🔗
We have \(\gexp{5}{1}{\otimes}=5\text{.}\) Thus \(\glog{5}{5}{\otimes}=1\text{.}\)
🔗

🔗
We have \(\gexp{5}{2}{\otimes}=5\otimes 5 = (5\cdot 5) \fmod 7=4\text{.}\) Thus \(\glog{5}{4}{\otimes}=2\text{.}\)
🔗

🔗
We have \(\gexp{5}{3}{\otimes}=4\otimes 5 = (4\cdot 5) \fmod 7=6\text{.}\) Thus \(\glog{5}{6}{\otimes}=3\text{.}\)
🔗

🔗
We have \(\gexp{5}{4}{\otimes}=6\otimes 5 = (6\cdot 5) \fmod 7=2\text{.}\) Thus \(\glog{5}{2}{\otimes}=4\text{.}\)
🔗

🔗
We have \(\gexp{5}{5}{\otimes}=2\otimes 5 = (2\cdot 5) \fmod 7=3\text{.}\) Thus \(\glog{5}{3}{\otimes}=5\text{.}\)
🔗

🔗

🔗

Exponentiation and discrete logarithm to the same base are inverse functions. This is illustrated in the next example.

🔗

Example 15.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{.}\) We have

\begin{equation*} e(0)=\gexp{3}{0}{\otimes}=1,\, e(1)=\gexp{3}{1}{\otimes}=3,\, e(2)=\gexp{3}{2}{\otimes}=4,\, e(3)=\gexp{3}{3}{\otimes}=2 \end{equation*}

🔗

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

\begin{equation*} l(1)=\glog{3}{1}{\otimes}=0,\, l(2)=\glog{3}{2}{\otimes}=3,\, l(3)=\glog{3}{1}{\otimes}=1,\, l(4)=\glog{3}{1}{\otimes}=0 \end{equation*}

🔗

As \(l(e(x))=x\) for all \(x\in\Z_5^\otimes\text{,}\) the function \(l\) is the inverse function of \(e\text{.}\)

🔗

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.

🔗

Problem 15.4.11. Finding \(\glog{3}{6}{\otimes}\) in \((\Z_{7}^\otimes,\otimes)\).

In the group \((\Z_{7}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 7\) find the discrete logarithm to base 3 of 6.

🔗

Solution.

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.

🔗

Problem 15.4.12. Finding \(\glog{7}{9}{\otimes}\) in \((\Z_{11}^\otimes,\otimes)\).

In the group \((\Z_{11}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 11\) find \(\glog{7}{9}{\otimes}\text{.}\)

🔗

Solution.

We need to find \(n\in\W\) such that \(\gexp{7}{n}{\otimes}=9\text{.}\) We compute

🔗

\(\gexp{7}{1}{\otimes}=7\)	\(\gexp{7}{2}{\otimes}=(7\cdot 7)\fmod 11=5\)
\(\gexp{7}{3}{\otimes}=5\otimes 7 =(5\cdot 7)\fmod 11=2\)	\(\gexp{7}{4}{\otimes}=(2\otimes 7)=(2\cdot 7)\fmod 11=3\)
\(\gexp{7}{5}{\otimes}=3\otimes 7 =(3\cdot 7)\fmod 11=10\)	\(\gexp{7}{6}{\otimes}=(10\otimes 7)=(10\cdot 7)\fmod 11=4\)
\(\gexp{7}{7}{\otimes}=4 \otimes 7 = (4\cdot 7)\fmod 11=6\)	\(\gexp{7}{8}{\otimes}=(6\otimes 7)=(6\cdot 7)\fmod 11=9\)

🔗

Thus \(\glog{7}{9}{\otimes}=8\text{.}\)

🔗

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.

🔗

Algorithm 15.4.13. Naive Discrete Logarithm.

Input: 🔗: A finite group \((G,\star)\text{,}\) \(b\in G\) and \(a\in G\)
🔗
Output: 🔗: 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.
🔗

let \(n:=0\)
🔗

🔗
let \(c:=1\)
🔗

🔗
repeat
🔗
1. if \(c=a\) then return \(n\)
  🔗
  
  🔗
2. let \(c:= c\star b\)
  🔗
  
  🔗
3. let \(n:= n+1\)
  🔗
  
  🔗
🔗
until \(n=\#G\)
🔗

🔗
return “the discrete logarithm to base \(b\) of \(a\) does not exist”
🔗

🔗

🔗

Next we illustrate with an example that computing powers using fast exponentiation is considerably faster than finding discrete logarithms with the naive method.

🔗

Problem 15.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{.}\)

Find \(\glog{2}{5}{\otimes}\text{.}\)
🔗

🔗
Count the number of group operation \(\otimes\) you need to find \(\glog{2}{5}{\otimes}\text{.}\)
🔗

🔗
How many group operations \(\otimes\) are needed to compute \(\gexp{2}{24}{\otimes}\) using fast exponentiation.
🔗

🔗

🔗

Solution.

We check all powers of \(2\) until we obtain \(5\text{.}\) We get:

🔗

\(\gexp{2}{1}{\otimes}=2\)	\(\gexp{2}{2}{\otimes}=2\otimes 2=4\)	\(\gexp{2}{3}{\otimes}=4\otimes 2=8\)	\(\gexp{2}{4}{\otimes}=8\otimes 2=16\)
\(\gexp{2}{5}{\otimes}=16\otimes 2=32\)	\(\gexp{2}{6}{\otimes}=32\otimes 2=64\)	\(\gexp{2}{7}{\otimes}=64\otimes 2=27\)	\(\gexp{2}{8}{\otimes}=27\otimes 2=54\)
\(\gexp{2}{9}{\otimes}=54\otimes 2=7\)	\(\gexp{2}{{10}}{\otimes}=7\otimes 2=14\)	\(\gexp{2}{{11}}{\otimes}=14\otimes 2=28\)	\(\gexp{2}{{12}}{\otimes}=18\otimes 2=56\)
\(\gexp{2}{{13}}{\otimes}=56\otimes 2=11\)	\(\gexp{2}{{14}}{\otimes}=11\otimes 2=22\)	\(\gexp{2}{{15}}{\otimes}=22\otimes 2=44\)	\(\gexp{2}{{16}}{\otimes}=44\otimes 2=88\)
\(\gexp{2}{{17}}{\otimes}=88\otimes 2=75\)	\(\gexp{2}{{18}}{\otimes}=75\otimes 2=49\)	\(\gexp{2}{{19}}{\otimes}=49\otimes 2=98\)	\(\gexp{2}{{20}}{\otimes}=98\otimes 2=95\)
\(\gexp{2}{{21}}{\otimes}=95\otimes 2=89\)	\(\gexp{2}{{22}}{\otimes}=89\otimes 2=77\)	\(\gexp{2}{{23}}{\otimes}=77\otimes 2=53\)	\(\gexp{2}{{24}}{\otimes}=53\otimes 2=5\)

🔗

Thus the discrete logarithm to base 2 of 5 is 24.

🔗

We found the solution with 23 group operations \(\otimes\text{.}\)
🔗

🔗
To compute \(\gexp{2}{24}{\otimes}\) using fast exponentiation we first write 24 as a sum of powers of 2. We find \(24=16+8=2^4+2^3\) and compute

\begin{equation*} \gexp{2}{2}{\otimes}=2\otimes 2=4,\;\gexp{2}{4}{\otimes}=4\otimes 4=16,\; \gexp{2}{8}{\otimes}=16\otimes 16=54,\;\gexp{2}{16}{\otimes}=54\otimes 54=88\text{.} \end{equation*}

These are 4 group operations \(\otimes\text{.}\) Now one more group operation \(\otimes\) yields

\begin{equation*} \gexp{2}{24}{\otimes}=\gexp{2}{16}{\otimes}\otimes\gexp{2}{8}{\otimes}=88\otimes 54=5\text{.} \end{equation*}

So we need \(5\) group operations \(\otimes\) to compute \(\gexp{2}{24}{\otimes}\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.3.5). In Problem 15.3.9, 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.

🔗

Prev Top Next