Theorem 15.8.
Let \((G,\star)\) be a group, \(b\in G\text{,}\) and \(n\in\N\text{.}\) The naive exponentiation algorithm (Algorithm 15.5) computes \(\gexp{b}{n}{\star}\) with \(n-1\) operations \(\star\text{.}\)
Section 15.2 Repeated Squaring
Because time is a valuable resource, we often look for ways of completing a given task as quickly as possible. In order to decide which way of completing the task is faster we compare the time needed.
In this course the tasks are computations and we formulate ways of completing them as strategies or algorithms. Depending on who follows the instruction (say a human being or a computer) the time needed to perform a computation differs. So instead of measuring time, we count the number of operations needed to compare how fast a strategy or an algorithm is. This count of operations usually depends on the numbers involved in the computation. For algorithms we give this count depending on the input. This process is called complexity analysis. To simplify the analysis of our algorithms we only count the number of the most involved operations, which in this section are multiplications or group operations.
Proof.
In Algorithm 15.5 the operation \(\star\) only occurs in step 4 Item 5.a in the repeat_until-loop. Assuming that \(n\neq0,1\text{,}\) in step 4 the variable \(i\) is set to \(1\text{.}\) From there, we enter into the repeat_until-loop.
After each operation \(\star\) in step 4 Item 5.a we add \(1\) to \(i\) in step 4 Item 5.b. Because the repeat_until-loop ends when \(i\) is equal to \(n\text{,}\) we follow the instructions in steps 4 Item 5.a and Item 4 Item 5.b exactly \(n-1\) times. Thus to compute \(\gexp{b}{n}{\star}\) with Algorithm 15.5 we need \(n-1\) operations \(\star\text{.}\)
This complexity analysis of the naive exponentiation algorithm also holds for the naive exponentiation algorithm for integers, Algorithm 2.44.
In Chapter 2, we gave two algorithms for computing \(c^4\) for some integer \(c\text{,}\) namely Algorithm 2.7 and Algorithm 2.25. Although the output of both algorithms was the same, the number of multiplications to compute the output differed. Algorithm 2.7 computes \(c^4=c\cdot c\cdot c\cdot c\) which needs three multiplications. Algorithm 2.25 first computes \(d:=c\cdot c\) and then \(c^4=d\cdot d\) which need two multiplications.
In this section we employ the idea behind the latter algorithm to compute powers of group elements in the case when the exponent is a power of 2. This strategy is called repeated squaring. We first demonstrate it with an example.
Example 15.9. Computing \(\gexp{6}{8}{\otimes}\) with repeated squaring.
In the group \((\Z_{11}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 11\) we compute \(\gexp{6}{8}{\otimes}\text{.}\) Instead of the naive exponentiation method that we employed in Example 15.4 we use repeated squaring. We first compute
\begin{equation*}
\gexp{6}{2}{\otimes}=6\otimes 6=(6\cdot 6)\fmod 11=36\fmod 11= 3
\end{equation*}
By Theorem 15.2 Item 2 we have
\begin{equation*}
\gexp{6}{4}{\otimes}=\gexp{6}{(2\cdot 2)}{\otimes}= \gexpp{\gexp{6}{2}{\otimes}}{2}{\otimes}= \gexp{6}{2}{\otimes}\otimes \gexp{6}{2}{\otimes}= 3\otimes 3=(3\cdot 3)\fmod 11 = 9 \fmod 11= 9\text{.}
\end{equation*}
Instead of the \(3\) operations \(\otimes\) in which we computed \(\gexp{6}{4}{\otimes}\) in Example 15.4 we have computed \(\gexp{6}{4}{\otimes}\) in \(2\) operations \(\otimes\text{.}\) By Theorem 15.2 Item 2 we have
\begin{equation*}
\gexp{6}{8}{\otimes}=\gexp{6}{(4\cdot 2)}{\otimes}= \gexpp{\gexp{6}{4}{\otimes}}{2}{\otimes}= \gexp{6}{4}{\otimes}\otimes \gexp{6}{4}{\otimes}= 9\otimes 9=(9\cdot 9)\fmod 11 = 81 \fmod 11= 4\text{.}
\end{equation*}
Instead of the \(7\) operations \(\otimes\) in which we computed \(\gexp{6}{8}{\otimes}\) in Example 15.4 we have computed \(\gexp{6}{8}{\otimes}\) in \(3\) operations \(\otimes\text{.}\)
In the video in Figure 15.10 we give another example for repeated squaring. We compute \(2^{16}\fmod 101\) and recall some properties of modular multiplication on the way.
When a power of a group element is given we can easily find its square.
Problem 15.11. Compute \(\gexp{19}{2048}{\otimes}\) given \(\gexp{19}{1024}{\otimes}\).
In the group \((\mathbb{Z}_{19843}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\bmod 19843\) we have \(\gexp{19}{1024}{\otimes}=2327\text{.}\) Find \(\gexp{19}{2048}{\otimes}\text{.}\)
Solution.
We notice that \(2048=2\cdot 1024\text{.}\) So we compute
\begin{align*}
\gexp{19}{2048}{\otimes}\amp=\gexpp{\gexp{19}{1024}{\otimes}}{2}{\otimes}=\gexp{2327}{2}{\otimes}\\
\amp =(2327\cdot 2327) \fmod 19843 =5414929 \fmod 19843 = 17633\text{.}
\end{align*}
In general squaring can be used to compute \(b^{2a}\) when \(b^a\) is known.
When using the repeated squaring strategy to compute a power in a group \((G,\star)\) we start with squaring the base \(b\) to obtain \(\gexp{b}{2}{\star}\text{.}\) Squaring \(\gexp{b}{2}{\star}\) yields \(\gexpp{\gexp{b}{2}{\star}}{2}{\star}=\gexp{b}{4}{\star}\text{.}\) Squaring \(\gexp{b}{4}{\star}\) yields \(\gexpp{\gexp{b}{4}{\star}}{2}{\star}=\gexp{b}{8}{\star}\) and so on. Each time we square the exponent doubles. That means that the exponents after squaring \(s\) times is the product of \(s\) copies of \(2\) which is equal to \(2^s\text{.}\) Thus we can use repeated squaring to compute powers of the form
\begin{equation*}
\gexp{b}{\displaystyle(2^s)}{\star}\text{.}
\end{equation*}
That is, the repeated squaring strategy works for any power, whose exponent is a power of 2.
Example 15.12. Computing \(\gexp{3}{32}{\otimes}\) with repeated squaring.
In the group \((\Z_{101}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 101\) we compute \(\gexp{3}{32}{\otimes}\) with repeated squaring. Note that \(32=2^5\text{.}\) We start with computing
\begin{equation*}
\gexp{3}{2}{\otimes}=3\otimes 3 = 9\text{.}
\end{equation*}
Now we use that \(\gexp{3}{4}{\otimes}=\gexp{3}{2\cdot 2}{\otimes}=\gexp{\left(\gexp{3}{2}{\otimes}\right)}{2}{\otimes}=\gexp{3}{2}{\otimes}\otimes\gexp{3}{2}{\otimes}\text{.}\) Replacing \(\gexp{3}{2}{\otimes}\) by 9 we get
\begin{equation*}
\gexp{3}{4}{\otimes}=\gexp{3}{2}{\otimes}\otimes\gexp{3}{2}{\otimes}=9\otimes 9=81\text{.}
\end{equation*}
Now we use that \(\gexp{3}{8}{\otimes}=\gexp{3}{4\cdot 2}{\otimes}=\gexpp{{\gexp{3}{4}{\otimes}}}{2}{\otimes}=\gexp{3}{4}{\otimes}\otimes\gexp{3}{4}{\otimes}\text{.}\) Replacing \(\gexp{3}{4}{\otimes}\) by 81 we get
\begin{equation*}
\gexp{3}{8}{\otimes}=\gexp{3}{4}{\otimes}\otimes\gexp{3}{4}{\otimes}=81\otimes 81=(81\cdot 81)\fmod 101 =6561\fmod 101=97\text{.}
\end{equation*}
Now we use that \(\gexp{3}{16}{\otimes}=\gexp{3}{8\cdot 2}{\otimes}=\gexpp{{\gexp{3}{8}{\otimes}}}{2}{\otimes}=\gexp{3}{8}{\otimes}\otimes\gexp{3}{8}{\otimes}\text{.}\) Replacing \(\gexp{3}{8}{\otimes}\) by 97 we get
\begin{equation*}
\gexp{3}{16}{\otimes}=\gexp{3}{8}{\otimes}\otimes\gexp{3}{8}{\otimes}=97\otimes 97=(97\cdot 97)\fmod 101 =9401\fmod 101=16\text{.}
\end{equation*}
Now we use that \(\gexp{3}{32}{\otimes}=\gexp{3}{16\cdot 2}{\otimes}=\gexpp{{\gexp{3}{16}{\otimes}}}{2}{\otimes}=\gexp{3}{16}{\otimes}\otimes\gexp{3}{16}{\otimes}\text{.}\) Replacing \(\gexp{3}{16}{\otimes}\) by 16 we get
\begin{equation*}
\gexp{3}{32}{\otimes}=\gexp{3}{16}{\otimes}\otimes\gexp{3}{16}{\otimes}=16\otimes 16=(16\cdot 16)\fmod 101 =256\fmod 101=54\text{.}
\end{equation*}
We have found that \(\gexp{3}{32}{\otimes}=54\text{.}\) While the above process may seem awkward, we only needed to evaluate the binary operation \(\otimes\) five times to compute the result. With the method from the previous section we would have needed 31 operations \(\otimes\text{.}\)
We formulate the repeated squaring strategy as an algorithm.
Algorithm 15.13. Repeated Squaring.
- Input:
- A group \((G,\star)\text{,}\) \(b\in G\text{,}\) and a non-negative integer \(s\)
- Output:
- \(\displaystyle \gexp{b}{2^s}{\star}\)
- if \(s=0\) then return \(b\)
- let \(i:=1\)
- let \(c:=b\star b\)
-
repeat
- let \(c:=c\star c\)
- let \(i:= i+1\)
- until \(i=s\)
- return \(c\)
In the video in Figure 15.14 we discuss the repeated squaring algorithm and give another example.
See how the idea of repeated squaring reduces the effort of exponentiation in Checkpoint 15.15.
Checkpoint 15.15. Repeated squaring.
Let \((G,\otimes)\) be a group and \(b\in G\text{.}\) We set \(b^{0\otimes}=e\) where \(e\in G\) is the identity of \((G,\otimes)\text{.}\) For \(n\in\mathbb{N}\) we set
\begin{equation*}
b^{n\otimes}=\underbrace{b\otimes b\otimes\dots\otimes b}_{\mbox{n copies of b}}.
\end{equation*}
In \((\mathbb{Z}_{83}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\bmod 83\) follow these steps to compute \(4^{32\otimes}\text{.}\)
\(4^{1\otimes}=\)
\(4^{2\otimes}=
4^{1\otimes}\otimes4^{1\otimes}=\) \(\otimes\)\(=\)
\(4^{4\otimes}=
4^{2\otimes}\otimes4^{2\otimes}=\) \(\otimes\)\(=\)
\(4^{8\otimes}=
4^{4\otimes}\otimes4^{4\otimes}=\) \(\otimes\)\(=\)
\(4^{16\otimes}=
4^{8\otimes}\otimes4^{8\otimes}=\) \(\otimes\)\(=\)
\(4^{32\otimes}=
4^{16\otimes}\otimes4^{16\otimes}=\) \(\otimes\)\(=\)
Hint.
We have \(b^{n\otimes}=b^n \bmod 83\text{.}\) Always compute \(\bmod 83\) before entering the answers.
To compute \(\gexp{b}{\displaystyle(2^s)}{\star}\) we compute a square \(s\) times. As each squaring needs on group operation \(\star\) we can compute \(\gexp{b}{\displaystyle(2^s)}{\star}\) with \(s\) operations \(\star\text{.}\) We have proven:
Theorem 15.16.
Let \(\star\) be a binary operation on a set \(G\) and \(b\in G\) and \(n\in N\text{.}\) Then, using repeated squaring, \(\gexp{b}{(2^n)}{\star}\) can be computed with \(n\) operations \(\star\text{.}\)
By Theorem 15.8 computing \(\gexp{a}{2^n}{\star}\) using the naive exponentiation algorithm (Algorithm 15.5)) needs \(2^n-1\) operations \(\star\text{.}\) So for \(n>1\) the repeated squaring strategy is faster.
Problem 15.17. Complexity of computing \(19^{128\otimes}\).
Let \(\otimes:\mathbb{Z}_{19843}^\otimes\times\mathbb{Z}_{19843}^\otimes\to\mathbb{Z}_{19843}^\otimes\) be the binary operation given by \(a\otimes b=(a\cdot b)\bmod 19843\text{.}\)
- How many operations \(\otimes\) are needed to compute \(19^{128\otimes}\) with the naive exponentiation method (repeated multiplication by \(19\)) ?
- How many operations \(\otimes\) are needed to compute \(19^{128\otimes}\) with the repeated squaring) method ?
Solution.
- By Theorem 15.8 \(128-1=127\) operations \(\otimes\) to compute \(19^{128\otimes}\) with the naive exponentiation algorithm.
- As \(128 = 2^{7}\) by Theorem 15.16 we need \(7\) operations \(\otimes\) to compute \(19^{128\otimes}\) using repeated squaring.
