Repeated Squaring

Subsection 5.2.3 Repeated Squaring

Let \(b\text{,}\) \(n\text{,}\) and \(m\) be positive integers. For cryptographic applications, it is important to compute \(b^n \bmod m\) efficiently. Note that in theory, the computation is easy. For example, we can compute

\begin{equation*} b^n = \underbrace{b \cdot b \cdots b}_{n\text{ times}}. \end{equation*}

Then divide the result by \(m\) to get the remainder. There are at least two problems with this in practice. The first is that computing \(b^n\) in this way requires \(n - 1\) multiplications. If \(n\) is large, this is slow. We can get around this using a method called fast exponentiation which we develop in this section and the following section.

🔗

Theorem 5.2.3.1.

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*}

Let \(k\in\NN\text{.}\) We can compute \(b^{(2^k)\otimes}=(b^{(2^k)})\bmod m\) with \(k\) operations \(\otimes\text{.}\)

🔗

Example 5.2.3.2. Modular powers.

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 set

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

We compute \(2^{16\otimes}=(2^{16}) \bmod 101\) following this definition of exponentiation.

\begin{align*} 2^{2\otimes} \amp =2\otimes 2 = (2\cdot 2)\bmod 101 = 4 \\ 2^{3\otimes} \amp =2\otimes 4 = (2\cdot 4)\bmod 101 = 8 \\ 2^{4\otimes} \amp =2\otimes 8 = (2\cdot 8)\bmod 101 = 16 \\ 2^{5\otimes} \amp =2\otimes 16 = (2\cdot 16)\bmod 101 = 32 \\ 2^{6\otimes} \amp =2\otimes 32 = (2\cdot 32)\bmod 101 = 64 \\ 2^{7\otimes} \amp =2\otimes 64 = (2\cdot 64)\bmod 101 = 128\bmod 101 = 27 \\ 2^{8\otimes} \amp =2\otimes 27 = (2\cdot 27)\bmod 101 = 54 \\ 2^{9\otimes} \amp =2\otimes 54 = (2\cdot 54)\bmod 101 = 108\bmod 101 = 7 \\ 2^{10\otimes} \amp =2\otimes 7 = (2\cdot 7)\bmod 101 = 14 \\ 2^{11\otimes} \amp =2\otimes 14 = (2\cdot 14)\bmod 101 = 28 \\ 2^{12\otimes} \amp =2\otimes 28 = (2\cdot 28)\bmod 101 = 56 \\ 2^{13\otimes} \amp =2\otimes 56 = (2\cdot 56)\bmod 101 = 112\bmod 101 = 11 \\ 2^{14\otimes} \amp =2\otimes 11 = (2\cdot 11)\bmod 101 = 22 \\ 2^{15\otimes} \amp =2\otimes 22 = (2\cdot 22)\bmod 101 = 44 \\ 2^{16\otimes} \amp =2\otimes 44 = (2\cdot 44)\bmod 101 = 88 \end{align*}

We have computed that \(2^{16\otimes}=(2^{16}) \bmod 101=88\) with \(15\) operations \(\otimes\text{.}\)

🔗

Example 5.2.3.3. Repeated squaring.

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 set

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

We have

\begin{align*} b^{2n\otimes}\amp =(b^{2n}) \bmod 101 =(b^{n})^2\bmod 101\\ \amp= (b^n\cdot b^n)\bmod 101=(b^{n\otimes})\otimes (b^{n\otimes}). \end{align*}

We compute \(2^{16\otimes}=(2^{16}) \bmod 101\) with a method called repeated squaring.

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

We have computed that \(2^{16\otimes}=(2^{16}) \bmod 101=88\) with \(4\) operations \(\otimes\text{.}\)

🔗

Theorem 5.2.3.4.

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*}

Let \(k\in\NN\text{.}\) We can compute \(b^{(2^k)\otimes}=(b^{(2^k)})\bmod m\) with \(k\) operations \(\otimes\text{.}\)

🔗

Proof.

For \(n\in\NN\) we have

\begin{equation*} b^{2n\otimes}=(b^{2n}) \bmod m=(b^{n})^2\bmod m = (b^n\cdot b^n)\bmod m=(b^{n\otimes})\otimes b^{n\otimes} \end{equation*}

To compute \(b^{(2^k)\otimes}\) we compute

\begin{align*} b^{2\otimes} \amp =b\otimes b \\ b^{2^2\otimes} \amp =b^{2\otimes} \otimes b^{2\otimes} \\ \amp \;\;\vdots \\ b^{2^{k-1}\otimes} \amp =b^{2^{k-2}\otimes} \otimes b^{2^{k-2}\otimes} \\ b^{2^{k}\otimes} \amp =b^{2^{k-1}\otimes} \otimes b^{2^{k-1}\otimes} \end{align*}

which needs \(k\) operations \(\otimes\text{.}\)

🔗

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

🔗

Listing 5.2.3.5.

🔗

def repeated_squaring(b,k,m):
  """
  compute b^(2^k) mod m
  """
  s = b # this will be the answer
  while k != 0:
    s = (s*s) % m
    k = k-1
  return a

Remark 5.2.3.6.

When we compute \(b^{(2^k)\otimes}\) using repeated squaring in the process we also compute

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

🔗

Figure 5.2.3.7. Su Doku. (`https://xkcd.com/74/`) This one is from the Red Belt collection, of ’medium’ difficulty
🔗

🔗

Prev Top Next