Fast exponentiation

Subsection 5.2.4 Fast exponentiation

We will develop the algorithm by first looking at a couple of examples.

Perhaps the most important observation is that we wrote the exponent as a sum of powers of \(2\) and that these are exactly the exponents of the numbers that we obtain from repeated squaring. In the following example we emphasize this step by first computing the base \(2\) expansion of the exponent.

🔗

Example 5.2.4.1. Fast exponentiation.

Compute \(3^{11}\text{.}\)

🔗

First, we compute the binary expansion of \(11 = (1011)_2\text{.}\) Then

\begin{equation*} 3^{11} = 3^{2^3 + 2^1 + 1} = 3^8 \cdot 3^2 \cdot 3. \end{equation*}

🔗

Notice that we can compute \(3^8\) as \((3^4)^2\text{.}\) Similarly, \(3^4 = (3^2)^2\text{.}\) We have by repeated squaring,

\begin{align*} 3 \amp = 3 \\ 3^2 \amp = 9 \\ 3^4 \amp = 9^2 = 81 \\ 3^8 \amp = 81^2 = 6561. \end{align*}

Thus, using the above,

\begin{equation*} 3^{11} = 3^{2^3+2^1+1}=3^8 \cdot 3^2 \cdot 3= 6561 \cdot 9 \cdot 3 = {177147}. \end{equation*}

In this computation, we cut the number of required multiplications in half. For larger exponents \(n\text{,}\) the savings are even more extreme.

🔗

If we compute \(\bmod\) after each operation the computation is more efficient. We can save even more time when we only care about the remainder modulo some integer.

🔗

Example 5.2.4.2. Modular fast exponentiation.

Compute \(3^{11} \bmod 7\text{.}\)

🔗

Solution.

As in Example 5.2.4.1, we will use the square and multiply technique to get the exponentiation faster. As before, we compute the binary expansion of \(11 = (1011)_2\text{.}\) Then

\begin{equation*} 3^{11} \bmod 7= 3^{2^3 + 2^1 + 1} \bmod 7 = (3^8 \cdot 3^2 \cdot 3 ) \bmod 7. \end{equation*}

We make additional time and memory savings by keeping the integers small. We achieve this by reducing mod \(7\) at every stage, since we only want the result modulo \(7\text{.}\)

🔗

We have by repeated squaring,

\begin{align*} 3 \bmod 7 \amp = 3 \\ 3^2 \bmod 7 \amp = 2 \\ 3^4 \bmod 7 \amp = 2^2 \bmod 7 = 4 \\ 3^8 \bmod 7 \amp = 4^2 \bmod 7 = 2. \end{align*}

Thus \(3^{11} \bmod 7 = 2 \cdot 2 \cdot 3 \bmod 7 = 5\text{.}\)

🔗

The fast exponentiation algorithm allows us to compute powerefficiently compute \(a^n\text{.}\)

🔗

Given positive integers \(a\) and \(n\) with \(m \gt 1\text{,}\) compute \(a^n\) by following these steps.

Compute the base \(2\) expansion of the exponent \(n\)
🔗

🔗
Make a list of successive squares \(p_i\text{,}\) where \(p_0 = a \bmod{m}\) and \(p_i = p_{i - 1}^2 \bmod{m}\) for \(1 \lt i\leq k\text{.}\)
🔗

🔗
Compute

\begin{equation*} p_0^{a_0}p_1^{a_1} \dots p_k^{a_k}\bmod{m}. \end{equation*}

🔗

🔗

Note that when \(a_i = 0\text{,}\) the term \(p_i^{a_i} = 1\) and so does not contribute to the product. S

🔗

When computing modulo some \(m\in\NN\) with \(m\ge 2\) we keep numbers small by reducing modulo \(m\) after each multipliction.

🔗

This approach is a non-recursive version of the algorithm from Example 2.4.4.4.

🔗

Theorem 5.2.4.3.

Let \(m\in\NN\) and let \(a\otimes b=(a\cdot b)\bmod m\text{.}\) For \(b\in\ZZ_{m}\) and \(n\in\NN\cup\{0\}\) we set

\begin{equation*} b^{n\otimes}=(b^n)\bmod m= \underbrace{b\otimes b\otimes\dots\otimes b}_{n \text{ copies of }b} \end{equation*}

We can compute \(b^{n\otimes}=(b^{n})\bmod m\) with less than \(2\cdot k\) operations \(\otimes\) if \(k+1\) is the number of digits of the base \(2\) representation of \(n\text{.}\)

🔗

Proof.

We write the base \(2\) expansion of \(n\) as

\begin{equation*} \displaystyle n=\sum_{i=0}^k r_i 2^i=r_0\cdot 2^0+r_1\cdot 2^1+\dots+ r_k\cdot 2^k \end{equation*}

We have

\begin{align} b^{n\otimes} \amp = b^{(r_0\cdot 2^0+r_1\cdot 2^1+\dots+ r_k\cdot 2^k)\otimes}\nonumber \notag\\ \amp =b^{(r_0\cdot 2^0)\otimes}\otimes b^{(r_1\cdot 2^1)\otimes}\otimes\dots\otimes b^{(r_k\cdot 2^k)\otimes}\nonumber \notag\\ \amp =\left(b^{(2^0)\otimes}\right)^{r_0}\otimes\tag{✶} \end{align}

In Theorem 5.2.3.4 we had seen that we can compute all of

\begin{equation*} b^{(2^0)\otimes}, b^{(2^1)\otimes},\dots, b^{(2^k)\otimes} \end{equation*}

with \(k\) operations \(\otimes\text{.}\)\\ There are at most \(k\) operations \(\otimes\) (outside the powers) in (✶). So in total we can compute \(b^{n\otimes}\) in at most \(2\cdot k\) operations \(\otimes\text{.}\)

🔗

Example 5.2.4.4. Modular fast exponentiation.

Let’s compute \(3^{67} \bmod{253}\text{.}\)

🔗

First we compute the base \(2\) expansion of \(67 = (1 0 0 0 0 1 1)_2\) as in Example 5.2.1.8. Note that this is seven digits (\(k = 6\)), so we need to compute the seven successive squares \(p_0, \dots p_6\text{.}\)

\begin{align*} p_0 \amp = 3 \bmod{253} = 3 \\ p_1 \amp = 3^2 \bmod{253} = 9 \\ p_2 \amp = 9^2 \bmod{253} = 81 \\ p_3 \amp = 81^2 \bmod{253} = 236 \\ p_4 \amp = 236^2 \bmod{253} = 36 \\ p_5 \amp = 36^2 \bmod{253} = 31 \\ p_6 \amp = 31^2 \bmod{253} = 202. \end{align*}

We summarize the computations so far.

\begin{equation*} \begin{array}{rrr} i \amp a_i \amp p_i\\ \hline 0\amp1\amp3 \bmod{253} =\fbox{\(3\)}\\ 1\amp1\amp3^2 \bmod{253} =\fbox{\(9\)}\\ 2\amp0\amp9^2 \bmod{253} = 81\\ 3\amp0\amp81^2 \bmod{253} = 236\\ 4\amp0\amp236^2 \bmod{253} = 36\\ 5\amp0\amp36^2 \bmod{253} = 31\\ 6\amp1\amp 31^2 \bmod{253} = \fbox{\(202\)}\\ \end{array} \end{equation*}

The terms corresponding to a \(1\) in the binary expansion of \(67\) have been boxed. It is these terms that we multiply together. It follows that

\begin{equation*} 3^{67} \bmod{253} = 3 \cdot 9 \cdot 202 \bmod{253} = 141. \end{equation*}

🔗

Example 5.2.4.5. Modular fast exponentiation.

Let the operation \(\otimes:\ZZ_{101}\times\ZZ_{101}\to\ZZ_{101}\) be given by \(a\otimes b=(a\cdot b)\bmod 101\text{.}\) For \(b\in\ZZ_{101}\) and \(n\in\NN\cup\{0\}\) we write

\begin{equation*} b^{n\otimes}= \underbrace{b\otimes b\otimes\dots\otimes b}_{n \text{ copies of }b} \end{equation*}

We compute \(2^{18\otimes}=(2^{18}) \bmod 101\text{.}\) In a previous example we had computed:

\begin{align*} 2^{2\otimes} \amp =2\otimes 2=4 \\ 2^{4\otimes} \amp =2^{2\otimes}\otimes2^{2\otimes}=4\otimes 4=16 \\ 2^{8\otimes} \amp =2^{4\otimes}\otimes2^{4\otimes}=16\otimes 16=256\bmod 101=54 \\ 2^{16\otimes} \amp =2^{8\otimes}\otimes2^{8\otimes}=54\otimes 54=2916 \bmod 101=88 \end{align*}

We have computed these values in \(4\) operations \(\otimes\text{.}\) Using this we get:

\begin{align*} 2^{18\otimes} \amp =2^{(2+16)\otimes} \\ \amp =2^{2\otimes}\otimes 2^{16\otimes} \\ \amp =4\otimes 88 \\ \amp =(4\cdot 88)\bmod 101 \\ \amp =352\bmod 101=49 \end{align*}

This took another \(2\) operations \(\otimes\text{.}\) So we computed \(2^{18\otimes}\) in \(4+2=6\) operations \(\otimes\text{.}\)

🔗

Computing \(2^{18\otimes}\) following the definition

\begin{equation*} 2^{18\otimes}= \underbrace{2\otimes 2\otimes\dots\otimes 2}_{18 \text{ copies of }2} \end{equation*}

needs \(17\) operations \(\otimes\text{.}\)

🔗

In our Python implementation of fast exponentiation 5.2.4.6 we go through the base \(2\) digits of the exponent in the same loop that we use to compute the powers \(s=b^{2^n}\) of the base \(b\text{.}\)

🔗

Since, in a computer, numbers are represented in base \(2\) representation looping over the digits of the base \(2\) representation, actually means going through the digits that are stored in the computer already.

🔗

The function in Listing 5.2.4.6 assumes that \(\mathtt{m}\in\NN\cup\{0\}\) and \(\mathtt{b}\in\NN-\{1\}\) and \(\mathtt{b}\in\NN\cup\{0\}\text{.}\)

🔗

Listing 5.2.4.6. Fast Exponentiation

🔗

def power_mod_fast(b,n,m):
  """
  compute b^n mod m
  """
  a = 1 # this will be the answer
  s = b # b^(2^i)
  while n != 0:
    q,r = divmod(n,2)
    if r==1:
      a = a*s % m
    n = q
    s = s*s % m
   return a

🔗

Prev Top Next