Theorem 15.2.1.
Let \((G,\star)\) be a group, \(b\in G\text{,}\) and \(n\in\N\text{.}\) The naive exponentiation algorithm (Algorithm 15.1.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. To decide which way of completing the task is faster we compare the time needed.
In this course, each task is a computation. We describe ways to complete a task as strategies or algorithms. The time needed can depend on who follows the instructions, such as a person or a computer. Instead of measuring time, we count the operations needed to compare how fast a strategy or algorithm is. This count usually depends on the numbers in the computation. For an algorithm, we give the count in terms of its input. This process is called complexity analysis. To keep the analysis simple, we count only the most involved operations. In this section, these are multiplications or group operations.
Proof.
In Algorithm 15.1.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. So to compute \(\gexp{b}{n}{\star}\) with Algorithm 15.1.5 we need \(n-1\) operations \(\star\text{.}\)
The same method for counting operations applies to the naive exponentiation algorithm for integers, Algorithm 2.6.1.
In Chapter 2, we gave two algorithms for computing \(c^4\) for some integer \(c\text{,}\) namely Algorithm 2.2.3 and Algorithm 2.4.3. Although the output of both algorithms was the same, the number of multiplications to compute the output differed. Algorithm 2.2.3 computes \(c^4=c\cdot c\cdot c\cdot c\) which needs three multiplications. Algorithm 2.4.3 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. First, we show it with an example.
Example 15.2.2. 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 used in Example 15.1.4 we use repeated squaring. First, we compute
\begin{equation*}
\gexp{6}{2}{\otimes}=6\otimes 6=(6\cdot 6)\fmod 11=36\fmod 11= 3
\end{equation*}
By Theorem 15.1.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*}
The \(3\) operations \(\otimes\) used to compute \(\gexp{6}{4}{\otimes}\) appear in Example 15.1.4. Here we computed \(\gexp{6}{4}{\otimes}\) with \(2\) operations \(\otimes\text{.}\) By Theorem 15.1.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*}
The \(7\) operations \(\otimes\) used to compute \(\gexp{6}{8}{\otimes}\) appear in Example 15.1.4. Here we computed \(\gexp{6}{8}{\otimes}\) with \(3\) operations \(\otimes\text{.}\)
The video in Figure 15.2.3 gives another example of repeated squaring. We compute \(2^{16}\fmod 101\) and review some properties of modular multiplication along the way.
When a power of a group element is given we can easily find its square.
Problem 15.2.4. 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{.}\)
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}\) gives \(\gexpp{\gexp{b}{2}{\star}}{2}{\star}=\gexp{b}{4}{\star}\text{.}\) Squaring \(\gexp{b}{4}{\star}\) gives \(\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{.}\) So 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.2.5. 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 write the repeated-squaring strategy as an algorithm.
Algorithm 15.2.6. Repeated Squaring.
- Input:
- Output:
- \(\displaystyle \gexp{b}{2^s}{\star}\)
-
repeat
The video in Figure 15.2.7 explains the repeated-squaring algorithm and gives another example.
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.2.8.
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.2.1, computing \(\gexp{a}{2^n}{\star}\) with the naive exponentiation algorithm (Algorithm 15.1.5) needs \(2^n-1\) operations \(\star\text{.}\) So, for \(n>1\text{,}\) repeated squaring is faster.
Problem 15.2.9. 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.2.1 \(128-1=127\) operations \(\otimes\) to compute \(19^{128\otimes}\) with the naive exponentiation algorithm.
-
As \(128 = 2^{7}\) by Theorem 15.2.8 we need \(7\) operations \(\otimes\) to compute \(19^{128\otimes}\) using repeated squaring.
