In Section 15.2 we saw that powers whose exponents are powers of two can be computed very efficiently. In the fast exponentiation strategy developed in this section we write any powers such that it can be computed as a product of powers obtained with repeated squaring.
In Section 11.2 on binary numbers, we saw that every natural number can be written as a sum of powers of \(2\text{.}\) By writing the exponent as a sum of powers of two, we can compute the value as a product of other values whose exponent is a power of 2. These are the powers we can compute efficiently with repeated squaring.
Example15.18.Computing \(3^{13}\) with \(5\) multiplications.
We compute \(3^{13}\) using only \(5\) multiplications.
The first multiplication gives us \(3^2 = 3 \cdot 3 = 9\text{.}\)
With the second multiplication we compute \(3^4 = 3^2 \cdot 3^2 = 9 \cdot 9 = 81\text{.}\)
With the third multiplication we compute \(3^8 = 3^4 \cdot 3^4 = 81 \cdot 81 = 6561\text{.}\)
The fourth and fifth multiplication yield the desired result
By squaring the result each time, we can efficiently compute the result when the exponents that are powers of two (\(2,4,8,16,\ldots\)). These numbers are exactly the place values of the base 2 (or binary) representation of integers. So writing an exponent as a sum of powers of two is the same as writing a number in base 2. To minimize the number of multiplications, we will always use the highest powers of two possible.
Now we look at example of computing powers in a group first using repeated multiplication and then using the method where we first write our exponent as a sum of powers of two, as in Example 15.18.
Example15.19.Naive versus fast exponentiation.
In the group \((\Z_{29}^\otimes,\otimes)\) we compute \(\gexp{3}{18}{\otimes}\) in two different ways.
We use the naive exponentiation algorithm (Algorithm 15.5). The computations will be easier than in the case of integers. Because we compute modulo 29 the numbers are smaller. We obtain:
Thus in \((\Z_{29}^\otimes,\otimes)\) we have \(\gexp{3}{18}{\star}=6\text{.}\)
We present a faster method. The exponent 18 written as a sum of powers of 2 is \(18=16+2=2^4+2\text{.}\) We obtain this either by educated guesses or by considering the base 2 representation
So it is sufficient to find \(\gexp{3}{2}{\otimes}\) and \(\gexp{3}{16}{\otimes}\) and multiply them to compute \(\gexp{3}{18}{\otimes}\text{.}\) We compute the highest power of these, namely \(\gexp{3}{16}{\otimes}\text{,}\) by repeated squaring. The power \(\gexp{3}{2}{\otimes}\) is also computed in this process.
Now we compute \(\gexp{3}{18}{\otimes}=\gexp{3}{2+16}{\otimes}=\gexp{3}{2}{\otimes}\otimes \gexp{3}{16}{\otimes}=9\otimes 20=180\fmod 29=6\text{.}\)
In Item 1 we computed \(\gexp{3}{18}{\otimes}\) with 17 group operations \(\otimes\text{,}\) while in Item 2 we needed 5 group operations \(\otimes\text{.}\) So the method in Item 2 is considerably faster than the method we used in Item 1.
So the powers of \(7\) that we need are \(\gexp{7}{2^6}{\otimes}=\gexp{7}{64}{\otimes}\) and \(\gexp{7}{2^1}{\otimes}=\gexp{7}{2}{\otimes}\text{.}\) Repeated squaring yields these powers of \(7\text{:}\)
Thus in \((\Z_{47}^\otimes,\otimes)\) we have \(\gexp{3}{40}{\otimes}=2\text{.}\)
We formulate the fast exponentiation strategy as an algorithm. Instead of first going through the repeated squaring and then multiplying the needed powers we combine the two steps in one loop. In this loop we square and at the same time compute whether or not that power of two is used in the exponent as a sum of powers of two.
Algorithm15.22.Fast Exponentiation.
Input:
A group \((G,\star)\text{,}\)\(b\in G\text{,}\) and \(n\in\N\)
Output:
\(\displaystyle \gexp{b}{n}{\star}\)
let\(a:=1\)
let\(c:=b\)
repeat
let\(r:=n\fmod 2\)
if\(r=1\)thenlet\(a:= a \star c\)
let\(n:=n\fdiv 2\)
let\(c:= c\star c\)
until\(n=0\)
return\(a\)
We discuss details of the algorithm in the video in Figure 15.23.
In the following example we compute a power with Algorithm 15.22.
Example15.24.Using the fast exponentiation algorithm.
With Algorithm 15.22 we compute \(\gexp{4}{25}{\otimes}\) in the group \((\Z_{53}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 53\text{.}\)
Initially we have \(b=5\) and \(n=25\) and set \(a:=1\) and \(c:=4\text{.}\) In the iterations of the loop the variables have the following values. In each row of the table we give the values of \(r\text{,}\)\(a\text{,}\)\(c\text{,}\) and \(n\) at the end of step 3.b.
\(r\)
\(a\)
\(n\)
\(c\)
1
25
4
\(25\fmod 2 =1\)
As \(r=1\) we set \(a\) to \(1\otimes 4=4\)
\(25\fdiv 2=12\)
\(4\otimes 4=16\)
\(12\fmod 2 =0\)
As \(r=0\) the value of a stays \(4\)
\(12\fdiv 2=6\)
\(16\otimes 16=44\)
\(6\fmod 2 =0\)
As \(r=0\) the value of a stays \(4\)
\(6\fdiv 2=3\)
\(44\otimes 44=28\)
\(3\fmod 2 =1\)
As \(r=1\) we set \(a\) to \(4\otimes 28=6\)
\(3\fdiv 2=1\)
\(28\otimes 28=42\)
\(1\fmod 2 =1\)
As \(r=1\) we set \(a\) to \(6\otimes 42=40\)
\(1\fdiv 2=0\)
So we get \(\gexp{4}{25}{\otimes}=4^{25}\fmod 53=40\text{.}\)
In Example 15.25 we specialize Algorithm 15.22 to the computation of powers in the groups \((\Z_{p}^\otimes,\otimes)\) where \(p\) is a prime number. Generate further examples and click in the steps of the algorithm to fill the table of variable values.
Example15.25.Fast exponentiation modulo m interactive.
Before we give the count of operations needed to compute a power with the fast exponentiation algorithm, we illustrate its efficiency in an example.
Problem15.26.Fast exponentiation and complexity.
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\) find \(\gexp{2}{24}{\otimes}\) using the fast exponentiation method. Count the number of group operations needed.
Solution.
We apply the fast exponentiation method. As \(24=8+16=2^{3}+2^{4}\) the highest power of the group element 2 that we need is \(\gexp{2}{16}{\otimes}\text{.}\) We compute:
We have computed \(\gexp{2}{24}{\otimes}\) with 5 operations \(\otimes\text{.}\)
With the naive exponentiation algorithm we would have needed \(23\) operations \(\otimes\text{.}\)
We now analyze the complexity of the fast exponentiation algorithm, that is, we determine how many operations are needed to compute a power with this algorithm.
Theorem15.27.
Let \(\star\) be a binary operation on a set \(G\) and \(b\in G\text{.}\) Let \(m\in \N\) and \(n\in\N\) such that \(m\le 2^n\text{.}\) Then, fast exponentiation, \(\gexp{b}{m}{\star}\) can be computed in at most \(2\cdot n\) operations \(\star\text{.}\)
Proof.
As \(m\le 2^n\) we can write \(\gexp{b}{m}{\star}\) as the product of powers of the form \(\gexp{b}{(2^k)}{\star}\) where \(k\le n\text{.}\) These powers can be computed with \(n\) operations \(\star\text{.}\) To evaluate the product we need at most \(n\) operations \(\star\text{.}\) Thus, with fast exponentiation, \(\gexp{b}{m}{\star}\) can be computed with at most \(n+n=2\cdot n\) operations \(\star\text{.}\)