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