 # PreTeXt Sample Book: Abstract Algebra (SAMPLE ONLY)

## Section4.4Large Powers of Integers

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^{1000000} }\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 $$2^{37398332 } \pmod{ 46389}\text{,}$$ we could very easily write the result down since it would be a number between 0 and 46,388. If we want to compute powers modulo $$n$$ quickly and efficiently, we will have to be clever. 1
The first thing to notice is that any number $$a$$ can be written as the sum of distinct powers of 2; 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.
We will compute $$271^{321} \pmod{ 481}\text{.}$$ Notice that
\begin{equation*} 321 = 2^0 +2^6 + 2^8\text{;} \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} = \mbox{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 \mbox{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 \mbox{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 RSA 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{.}$$

### Remark4.4.2.Sage.

Sage support for cyclic groups is a little spotty — but we can still make effective use of Sage and perhaps this situation could change soon.
The results in this section are needed only in Chapter 2 (not really).