Skip to main content
Logo image

PreTeXt Sample Book: Abstract Algebra (SAMPLE ONLY)

Section 2.4 Large Powers of Integers

View Source
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.
The results in this section are needed only in Chapter I.2 (not really).
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.

Example 2.4.1. Repeated Squares.

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*}
\begin{equation*} 271^{ 2^8 } \equiv 16 \pmod{ 481}\text{.} \end{equation*}
\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{.}\)

Remark 2.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.