Skip to main content

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.

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. Thus to compute \(\gexp{b}{n}{\star}\) with Algorithm 15.1.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.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. We first demonstrate it with an example.

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.1.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.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*}

Instead of the \(3\) operations \(\otimes\) in which we computed \(\gexp{6}{4}{\otimes}\) in Example 15.1.4 we have computed \(\gexp{6}{4}{\otimes}\) in \(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*}

Instead of the \(7\) operations \(\otimes\) in which we computed \(\gexp{6}{8}{\otimes}\) in Example 15.1.4 we have computed \(\gexp{6}{8}{\otimes}\) in \(3\) operations \(\otimes\text{.}\)

In the video in Figure 15.2.3 we give another example for repeated squaring. We compute \(2^{16}\fmod 101\) and recall some properties of modular multiplication on the way.

Figure 15.2.3. Repeated Squaring by Frances Clerk

When a power of a group element is given we can easily find its square.

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.

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.

In the video in Figure 15.2.7 we discuss the repeated squaring algorithm and give another example.

Figure 15.2.7. Repeated Squaring (Algorithm) by Matt Farmer and Stephen Steward

See how the idea of repeated squaring reduces the effort of exponentiation in Checkpoint 15.2.8.

Alice and Bob use the Diffie Hellman key exchange to generate a shared secret.

Alice and Bob: The Group

For their Diffie Hellman key exchange Alice and Bob agree to work in the group of \((\mathbb{Z}^\otimes_{29},\otimes)\) where \(a\otimes b=(a\cdot b)\bmod 29\text{.}\) They also agree on the generator \(g=2\text{.}\)

Alice: Secret

Alice chooses her secret \(a=3\) and sends \(A=g^{a\otimes}=(g^a)\bmod 29=\) to Bob.

Bob: Secret

Bob chooses his secret \(b=4\) and sends \(B=g^{b\otimes}=(g^b)\bmod 29=\) to Alice.

Alice: Shared Secret

Alice receives \(B=\) from Bob, and she computes the shared secret \(B^{a\otimes}=(B^a)\bmod 29=\)

Bob: Shared Secret

Bob receives \(A=\) from Alice, and he computes the shared secret \(A^{b\otimes}=(A^b)\bmod 29=\)

Alice and Bob: Shared Secret

Now Alice and Bob share the secret .

Answer 1.

\(8\)

Answer 2.

\(16\)

Answer 3.

\(16\)

Answer 4.

\(7\)

Answer 5.

\(8\)

Answer 6.

\(7\)

Answer 7.

\(7\)

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:

By Theorem 15.2.1 computing \(\gexp{a}{2^n}{\star}\) using the naive exponentiation algorithm (Algorithm 15.1.5)) needs \(2^n-1\) operations \(\star\text{.}\) So for \(n>1\) the repeated squaring strategy is faster.

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

  1. How many operations \(\otimes\) are needed to compute \(19^{128\otimes}\) with the naive exponentiation method (repeated multiplication by \(19\)) ?

  2. How many operations \(\otimes\) are needed to compute \(19^{128\otimes}\) with the repeated squaring) method ?

Solution.
  1. By Theorem 15.2.1 \(128-1=127\) operations \(\otimes\) to compute \(19^{128\otimes}\) with the naive exponentiation algorithm.

  2. As \(128 = 2^{7}\) by Theorem 15.2.9 we need \(7\) operations \(\otimes\) to compute \(19^{128\otimes}\) using repeated squaring.