Fast Exponentiation

Section 15.3 Fast Exponentiation

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.

Example 15.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

\begin{equation*} 3^{13} = 3\cdot 3^4 \cdot 3^8 = 3 \cdot 81 \cdot 6561 = 243 \cdot 6561 = 1594323\text{.} \end{equation*}

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.

Example 15.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:

\begin{align*} \gexp{3}{1}{\otimes}\amp = 3\\ \gexp{3}{2}{\otimes}\amp = 3\otimes 3=9\\ \gexp{3}{3}{\otimes}\amp = 9\otimes 3=27\\ \gexp{3}{4}{\otimes}\amp = 27\otimes3=81\fmod 29=23\\ \gexp{3}{5}{\otimes}\amp = 23\otimes3=69\fmod 29=11\\ \gexp{3}{6}{\otimes}\amp = 11\otimes 3=33\fmod 29=4\\ \gexp{3}{7}{\otimes}\amp = 4\otimes 3=12\\ \gexp{3}{8}{\otimes}\amp = 12\otimes 3=36\fmod 29=7\\ \gexp{3}{9}{\otimes}\amp = 7\otimes 3=21\\ \gexp{3}{{10}}{\otimes}\amp = 21\otimes 3=63\fmod 29=5\\ \gexp{3}{{11}}{\otimes}\amp = 5\otimes 3=15\\ \gexp{3}{{12}}{\otimes}\amp = 15\otimes 3=45\fmod29=16\\ \gexp{3}{{13}}{\otimes}\amp = 16\otimes 3=48\fmod 29=19\\ \gexp{3}{{14}}{\otimes}\amp = 19\otimes 3=57\fmod 29=28\\ \gexp{3}{{15}}{\otimes}\amp = 28\otimes 3=84\fmod 29=26\\ \gexp{3}{{16}}{\otimes}\amp = 26\otimes 3=78\fmod 29=20\\ \gexp{3}{{17}}{\otimes}\amp = 20\otimes 3=60\fmod29=2\\ \gexp{3}{{18}}{\otimes}\amp = 2\otimes 3=6 \end{align*}

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

\begin{equation*} 18=10010_2=1\cdot 2^{4}+0\cdot 2^3 +0\cdot 2^2+1\cdot 2+0\cdot 1\text{.} \end{equation*}

With the rules of exponentiation we get

\begin{equation*} \gexp{3}{18}{\otimes}=\gexp{3}{(2+16)}{\otimes}=\gexp{3}{2}{\otimes}\otimes \gexp{3}{16}{\otimes}\text{.} \end{equation*}

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.

\begin{align*} \gexp{3}{2}{\otimes}\amp =3\otimes 3=9\\ \gexp{3}{4}{\otimes}\amp =\gexp{(\gexp{3}{2}{\otimes})}{2}{\otimes}=9\otimes9=81\fmod 29=23\\ \gexp{3}{8}{\otimes}\amp =\gexp{(\gexp{3}{4}{\otimes})}{2}{\otimes}=23\otimes 23=529\fmod 29=7\\ \gexp{3}{16}{\otimes}\amp =\gexp{(\gexp{3}{8}{\otimes})}{2}{\otimes}=7\otimes 7=49\fmod 29=20\text{.} \end{align*}

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.

We call the method used in Example 15.19 Item 2 fast exponentiation.

Problem 15.20. Compute \(7^{66}\fmod 101\) using fast exponentiation.

In the group \((\Z_{101}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 101\) compute \(\gexp{7}{66}{\otimes}\text{.}\)

Solution.

First compute the base \(2\) expansion of \(66\) and obtain

\begin{equation*} 66=(1\cdot 2^6)+(0\cdot 2^5)+(0\cdot 2^4)+(0\cdot 2^3)+(0\cdot 2^2)+(1\cdot2^1)+(0\cdot 2^0)\text{.} \end{equation*}

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

\begin{align*} \gexp{7}{2}{\otimes}\amp =7\otimes 7=49\fmod 101=49\\ \gexp{7}{4}{\otimes}\amp =\gexp{7}{2}{\otimes}\otimes \gexp{7}{2}{\otimes}=49\otimes 49=2401\fmod 101=78\\ \gexp{7}{8}{\otimes}\amp =\gexp{7}{4}{\otimes}\otimes \gexp{7}{4}{\otimes}=78\otimes 78=6084\fmod 101=24\\ \gexp{7}{{16}}{\otimes}\amp =\gexp{7}{8}{\otimes}\otimes \gexp{7}{8}{\otimes}=24\otimes 24=576\fmod 101=71\\ \gexp{7}{{32}}{\otimes}\amp =\gexp{7}{{16}}{\otimes}\otimes \gexp{7}{{16}}{\otimes}=71\otimes 71=5041\fmod 101=92\\ \gexp{7}{{64}}{\otimes}\amp =\gexp{7}{{32}}{\otimes}\otimes \gexp{7}{{32}}{\otimes}=92\otimes 92=8464\fmod 101=81 \end{align*}

Multiplying the powers of \(7\) whose exponents occur in the base \(2\) expansion of \(66=64+2\) we obtain

\begin{equation*} \gexp{7}{{66}}{\otimes}=\gexp{7}{{64}}{\otimes}\otimes \gexp{7}{2}{\otimes}=81\otimes 49=3969\fmod 101=30\text{.} \end{equation*}

When the powers computed by repeated squaring are already other powers can be composed form these as demonstrated in the following problem.

Problem 15.21. Fast exponentiation given certain powers.

In the group \((\Z_{47}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 47\) we have

\begin{equation*} \gexp{3}{1}{\otimes}=3,\, \gexp{3}{2}{\otimes}=9,\, \gexp{3}{4}{\otimes}= 34,\, \gexp{3}{8}{\otimes}= 28,\, \gexp{3}{16}{\otimes}= 32,\, \gexp{3}{32}{\otimes}= 37 \end{equation*}

With this information compute \(\gexp{3}{40}{\otimes}\) by fast exponentiation.

Solution.

First we determine which powers of \(3\) we need to compute \(\gexp{3}{40}{\otimes}\text{.}\) The base \(2\) expansion of the exponent \(40\) is

\begin{equation*} 30= (1\cdot 2^5)+ (0\cdot 2^4)+ (1\cdot 2^3)+ (0\cdot 2^2)+ (0\cdot 2^1)+ (0\cdot 2^0)\text{.} \end{equation*}

Thus the powers of \(3\) that we need are

\begin{equation*} \gexp{3}{2^5}{\otimes}=\gexp{3}{32}{\otimes} \text{ and } \gexp{3}{2^3}{\otimes}=\gexp{3}{8}{\otimes} \end{equation*}

With the powers of \(3\) given in the problem we obtain

\begin{equation*} \gexp{3}{40}{\otimes}= \gexp{3}{32}{\otimes}\otimes \gexp{3}{8}{\otimes} = 37\otimes 28 =1036\fmod 47=2\text{.} \end{equation*}

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.

Algorithm 15.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
1. let \(r:=n\fmod 2\)
2. if \(r=1\) then let \(a:= a \star c\)
3. let \(n:=n\fdiv 2\)
4. let \(c:= c\star c\)
until \(n=0\)
return \(a\)

We discuss details of the algorithm in the video in Figure 15.23.

Figure 15.23. Fast Exponentiation (Algorithm) by Matt Farmer and Stephen Steward

In the following example we compute a power with Algorithm 15.22.

Example 15.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.

Example 15.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.

Problem 15.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:

\(\gexp{2}{2}{\otimes}=2\otimes 2=4\)

\(\gexp{2}{4}{\otimes}=\gexp{2}{2}{\otimes}\otimes\gexp{2}{2}{\otimes}=4\otimes 4=16\)

\(\gexp{2}{8}{\otimes}=\gexp{2}{4}{\otimes}\otimes \gexp{2}{4}{\otimes}=16\otimes 16=54\)

\(\gexp{2}{16}{\otimes}=\gexp{2}{8}{\otimes}\otimes \gexp{2}{8}{\otimes}=54\otimes 54=88\)

Thus \(\gexp{2}{24}{\otimes}=\gexp{2}{(8+16)}{\otimes}=\gexp{2}{8}{\otimes}\otimes \gexp{2}{16}{\otimes}=54\otimes 88=5\text{.}\)

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.

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

Prev Top Next