$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section4.3The Method of Repeated Squares

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} }. \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}, \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 7

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}, \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}. \end{gather*}

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

###### Example4.28

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}. \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} = \text{73,441} \equiv 329 \pmod{ 481}. \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}. \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}. \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}. \end{align*}

The method of repeated squares will prove to be a very useful tool when we explore RSA cryptography in Chapter 7. 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{.}$