Skip to main content

Section 12.4 The Method of Repeated Squares

The method of repeated squares will prove to be a very useful tool in cryptography. To encode and decode messages in a reasonable manner under this scheme, it is necessary to be able to quickly compute large powers of integers mod \(n\text{.}\)

Computing large powers can be very time-consuming. Just as anyone can compute \(2^2\) or \(2^8\text{,}\) everyone knows how to compute

\begin{equation*} 2^{2^{1{,}000{,}000} }\text{.} \end{equation*}

However, such numbers are so large that we do not want to attempt the calculations; moreover, past a certain point the computations would not be feasible even if we had every computer in the world at our disposal. Even writing down the decimal representation of a very large number may not be reasonable. It could be thousands or even millions of digits long. However, if we could compute something like

\begin{equation*} 2^{37{,}398{,}332 } \pmod{ 46{,}389}\text{,} \end{equation*}

we could very easily write the result down since it would be a number between \(0\) and \(46{,}388\text{.}\) If we want to compute powers modulo \(n\) quickly and efficiently, we will have to be clever. 1 

The results in this section are needed only in Chapter 12

The first thing to notice is that any number \(a\) can be written as the sum of distinct powers of \(2\text{;}\) that is, we can write

\begin{equation*} a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}\text{,} \end{equation*}

where \(k_1 \lt k_2 \lt \cdots \lt k_n\text{.}\) This is just the binary representation of \(a\text{.}\) For example, the binary representation of 57 is 111001, since we can write \(57 = 2^0 + 2^3 + 2^4 + 2^5\text{.}\)

The laws of exponents still work in \({\mathbb Z}_n\text{;}\) that is, if \(b \equiv a^x \pmod{ n}\) and \(c \equiv a^y \pmod{ n}\text{,}\) then \(bc \equiv a^{x+y} \pmod{ n}\text{.}\) We can compute \(a^{2^k} \pmod{ n}\) in \(k\) multiplications by computing

\begin{gather*} a^{2^0} \pmod{ n}\\ a^{2^1} \pmod{ n }\\ \vdots\\ a^{2^k} \pmod{ n}\text{.} \end{gather*}

Each step involves squaring the answer obtained in the previous step, dividing by \(n\text{,}\) and taking the remainder.

Example 12.6.

We will compute \(271^{321} \pmod{ 481}\text{.}\) Notice that

\begin{equation*} 321 = 2^0 +2^6 + 2^8; \end{equation*}

hence, computing \(271^{ 321} \pmod{ 481}\) is the same as computing

\begin{equation*} 271^{ 2^0 +2^6 + 2^8 } \equiv 271^{ 2^0 } \cdot 271^{2^6 } \cdot 271^{ 2^8 } \pmod{ 481}\text{.} \end{equation*}

So it will suffice to compute \(271^{ 2^i } \pmod{ 481}\) where \(i = 0, 6, 8\text{.}\) It is very easy to see that

\begin{equation*} 271^{ 2^1} = 73{,}441 \equiv 329 \pmod{ 481}\text{.} \end{equation*}

We can square this result to obtain a value for \(271^{ 2^2} \pmod{481}\text{:}\)

\begin{align*} 271^{ 2^2} & \equiv (271^{ 2^1})^2 \pmod{ 481}\\ & \equiv (329)^2 \pmod{481}\\ & \equiv 108{,}241 \pmod{481}\\ & \equiv 16 \pmod{481}\text{.} \end{align*}

We are using the fact that \((a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}\text{.}\) Continuing, we can calculate

\begin{equation*} 271^{ 2^6 } \equiv 419 \pmod{481} \end{equation*}

and

\begin{equation*} 271^{ 2^8 } \equiv 16 \pmod{481}\text{.} \end{equation*}

Therefore,

\begin{align*} 271^{ 321} & \equiv 271^{ 2^0 +2^6 + 2^8 } \pmod{481}\\ & \equiv 271^{ 2^0 } \cdot 271^{ 2^6 } \cdot 271^{ 2^8 } \pmod{481}\\ & \equiv 271 \cdot 419 \cdot 16 \pmod{ 481}\\ & \equiv 1{,}816{,}784 \pmod{ 481}\\ & \equiv 47 \pmod{ 481}\text{.} \end{align*}