The fast powering algorithm

Section 2.4 The fast powering algorithm

Cryptosystems depend on operations with deeply asymmetric computability: in one direction we want the computations to be “easy” and in the other, essentially impossible. We will see that one such operation is taking repeated multiplications by the same integer \(g\text{,}\) the process of exponentiation. The idea is to take an integer \(g\) inside of \(\Z_n\) and raise \(g\) to some large power \(M\text{.}\)

The naive approach to this problem is to performs this process recursively: \(g_1 = g, g_2 = g\cdot g_1, \ldots, g_k = g \cdot g_{k-1} = g^k\text{.}\)

When the exponent in question is large, say on the order of \(2^{1000}\text{,}\) this process requires lengths of time on the order of the age of the universe. Indeed, this quality is why it is difficult to reverse a modular exponent (a process called a discrete logarithm that we will discuss in more detail soon).

To perform exponentiation quickly, we will use a binary expansion of the exponent combined with the observation that we can use repeated squarings to compute the total exponent. For example, consider the problem of computing \(3^{11} \bmod 13\text{.}\) First, we decompose the exponent \(11\) into a binary representation (this can by done in python with the bin command, which gives the binary form of the number).

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

Thus,

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

It is easy to compute the sequence

\begin{equation*} 3^{2^0}, 3^{2^1}, 3^{2^2}, \ldots \end{equation*}

because each term is the square of the previous term. Furthermore, while exponential functions grow in size very quickly (easily outside the typical storage available in a computer in as few as 200 or so squarings), we can take the results mod 13 at each step.

Thus, our sequence would read

\begin{equation*} 3^{2^0} = 3, \hspace{10pt} 3^{2^1} = 3^2 = 9, \hspace{10pt} 3^{2^2} = 9^2 = 81 = 3, \hspace{10pt} 3^{2^3} = 3^2 = 9. \end{equation*}

Now, we perform the computation

\begin{equation*} 3^{11} = 3^{2^0} \cdot 3^{2^1} \cdot 3^{2^3} = 3 \cdot 9 \cdot 9 \bmod 13 = 9 \bmod 13. \end{equation*}

Now, look at the result of the same computation in python using the bin command:

We can codify this idea in the Fast Powering Algorithm:

Algorithm 2.4.1. (Fast Powering Algorithm).

Consider the exponential \(g^k \bmod N\text{.}\)

Compute the binary expansion of the exponent \(k\text{:}\)

\begin{equation*} k = k_0 + k_1 \cdot 2 + k_2 \cdot 2^2 + \ldots + k_r \cdot 2^r \end{equation*}

where the coefficients \(k_i\) can be either 0 or 1, and we assume that \(k_r = 1\text{.}\)
Compute the powers \(g^{2^i} \bmod N\) for \(0 \leq i \leq r\) by repeating squaring:

\begin{align*} a_0 \amp= g \bmod N \\ a_1 \amp= a_0^2 = g^2 \bmod N \\ a_2 \amp= a_1^2 = g^{2^2} \bmod N\\ \vdots \amp \\ a_r \amp= a_{r-1}^2 = g^{2^r} \bmod N. \end{align*}
Compute \(g^k\) with

\begin{equation*} g^k = a_0^{k_0} \cdot a_1^{k_1} \cdot \ldots \cdot a_r^{k_r} \end{equation*}

where the exponents \(k_i\) determine if a particular power of \(g\) is present in the computation, as \(k_i\) is either 1 or 0.

In python, using the example of \(3^{11} \bmod 13\text{,}\) we could write the following program:

Working with binary numbers in python from a computation standpoint is going to require removing the “0b” segment at the front of the number (the string indicates that the format of the number is binary). Python makes it easy to strip this segment using array slicing. (The previous cell must have been executed to run the next one.)

Now we can pick out the array elements we need. Note that there is a complication arising from the fact that the squares array begins with \(3^{2^0}\text{,}\) but the binary representation of \(11\) reads the opposite direction, from \(2^3\) down to \(2^0\text{.}\)

Exercises Exercises

1.

Implement the fast powering algorithm in python as a function that takes as input a base \(g\text{,}\) a power \(x\text{,}\) and a mod \(n\) and produces as output \(g^x \bmod n\text{.}\) You may wish to use the python function bin(n) which returns the binary representation as a string of 1s and 0s. (You can view this string as the values of the coefficients \(k_i\) in the description of the algorithm above. )