4.3: The Method of Repeated Squares

Last updated
Save as PDF

Page ID: 81052

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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

\[ 2^{2^{1{,}000{,}000} }\text{.} \nonumber \]

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

\[ 2^{37{,}398{,}332 } \pmod{ 46{,}389}\text{,} \nonumber \]

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.¹

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

\[ a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}\text{,} \nonumber \]

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 4.28

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

\[ 321 = 2^0 +2^6 + 2^8; \nonumber \]

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

\[ 271^{ 2^0 +2^6 + 2^8 } \equiv 271^{ 2^0 } \cdot 271^{2^6 } \cdot 271^{ 2^8 } \pmod{ 481}\text{.} \nonumber \]

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

\[ 271^{ 2^1} = 73{,}441 \equiv 329 \pmod{ 481}\text{.} \nonumber \]

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

\[ 271^{ 2^6 } \equiv 419 \pmod{481} \nonumber \]

and

\[ 271^{ 2^8 } \equiv 16 \pmod{481}\text{.} \nonumber \]

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

The method of repeated squares will prove to be a very useful tool when we explore 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{.}\)