<section>
<title>Large Powers of Integers</title>
<p>Computing large powers can be very time-consuming. Just as anyone can compute <m>2^2</m> or <m>2^8</m>, everyone knows how to compute
<md>2^{2^{1000000} }</md>.
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 <m>2^{37398332 } \pmod{ 46389}</m>, 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 <m>n</m> quickly and efficiently, we will have to be clever.<fn>The results in this section are needed only in <xref ref="integers"/> (not really).</fn></p>
<p>The first thing to notice is that any number <m>a</m> can be written as the sum of distinct powers of 2; that is, we can write <md>a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}</md>, where <m>k_1 \lt k_2 \lt \cdots \lt k_n</m>. This is just the binary representation of <m>a</m>. For example, the binary representation of 57 is 111001, since we can write <m>57 = 2^0 + 2^3 + 2^4 + 2^5</m>.</p>
<p>The laws of exponents still work in <m>{\mathbb Z}_n</m>; that is, if <m>b \equiv a^x \pmod{ n}</m> and <m>c \equiv a^y \pmod{ n}</m>, then <m>bc \equiv a^{x+y} \pmod{ n}</m>. We can compute <m>a^{2^k} \pmod{ n}</m> in <m>k</m> multiplications by computing<md>
<mrow>a^{2^0} \pmod{ n}</mrow>
<mrow>a^{2^1} \pmod{ n }</mrow>
<mrow>\vdots</mrow>
<mrow>a^{2^k} \pmod{ n}</mrow>
</md>. Each step involves squaring the answer obtained in the previous step, dividing by <m>n</m>, and taking the remainder.</p>
<example xml:id="example-cyclic-repeated-squares">
<title>Repeated Squares</title>
<p>We will compute <m>271^{321} \pmod{ 481}</m>. Notice that <md>321 = 2^0 +2^6 + 2^8</md>; hence, computing <m>271^{321} \pmod{ 481}</m> is the same as computing <md>271^{2^0 +2^6 + 2^8 } \equiv 271^{2^0} \cdot 271^{2^6} \cdot 271^{2^8} \pmod{481}</md>. So it will suffice to compute <m>271^{2^i} \pmod{481}</m> where <m>i = 0, 6, 8</m>. It is very easy to see that <md>271^{2^1} = \mbox{73,441} \equiv 329 \pmod{481}</md>. We can square this result to obtain a value for <m>271^{2^2} \pmod{481}</m>:<md>
<mrow>271^{ 2^2} & \equiv (271^{ 2^1})^2 \pmod{ 481}</mrow>
<mrow>& \equiv (329)^2 \pmod{ 481}</mrow>
<mrow>& \equiv \mbox{108,241} \pmod{ 481}</mrow>
<mrow>& \equiv 16 \pmod{ 481}</mrow>
</md>. We are using the fact that <m>(a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}</m>. Continuing, we can calculate <md>271^{ 2^6 } \equiv 419 \pmod{ 481}</md> and <md>271^{ 2^8 } \equiv 16 \pmod{ 481}</md>. Therefore,<md>
<mrow>271^{ 321} & \equiv 271^{ 2^0 +2^6 + 2^8 } \pmod{ 481}</mrow>
<mrow>& \equiv 271^{ 2^0 } \cdot 271^{ 2^6 } \cdot 271^{ 2^8 } \pmod{ 481}</mrow>
<mrow>& \equiv 271 \cdot 419 \cdot 16 \pmod{ 481}</mrow>
<mrow>& \equiv \mbox{1,816,784} \pmod{ 481}</mrow>
<mrow>& \equiv 47 \pmod{ 481}</mrow>
</md>.</p>
</example>
<!-- Reformatted example. TWJ 2/5/2013 -->
<p> The method of repeated squares will prove to be a very useful tool when we explore <acro>RSA</acro> 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 <m>n</m>.</p>
<remark>
<title>Sage</title>
<p>Sage support for cyclic groups is a little spotty <mdash/> but we can still make effective use of Sage and perhaps this situation could change soon.</p>
</remark>
</section>
Section 4.4 Large Powers of Integers
View Source for section
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 results in this section are needed only in Chapter 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 4.4.1. Repeated Squares.
View Source for example
<example xml:id="example-cyclic-repeated-squares">
<title>Repeated Squares</title>
<p>We will compute <m>271^{321} \pmod{ 481}</m>. Notice that <md>321 = 2^0 +2^6 + 2^8</md>; hence, computing <m>271^{321} \pmod{ 481}</m> is the same as computing <md>271^{2^0 +2^6 + 2^8 } \equiv 271^{2^0} \cdot 271^{2^6} \cdot 271^{2^8} \pmod{481}</md>. So it will suffice to compute <m>271^{2^i} \pmod{481}</m> where <m>i = 0, 6, 8</m>. It is very easy to see that <md>271^{2^1} = \mbox{73,441} \equiv 329 \pmod{481}</md>. We can square this result to obtain a value for <m>271^{2^2} \pmod{481}</m>:<md>
<mrow>271^{ 2^2} & \equiv (271^{ 2^1})^2 \pmod{ 481}</mrow>
<mrow>& \equiv (329)^2 \pmod{ 481}</mrow>
<mrow>& \equiv \mbox{108,241} \pmod{ 481}</mrow>
<mrow>& \equiv 16 \pmod{ 481}</mrow>
</md>. We are using the fact that <m>(a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}</m>. Continuing, we can calculate <md>271^{ 2^6 } \equiv 419 \pmod{ 481}</md> and <md>271^{ 2^8 } \equiv 16 \pmod{ 481}</md>. Therefore,<md>
<mrow>271^{ 321} & \equiv 271^{ 2^0 +2^6 + 2^8 } \pmod{ 481}</mrow>
<mrow>& \equiv 271^{ 2^0 } \cdot 271^{ 2^6 } \cdot 271^{ 2^8 } \pmod{ 481}</mrow>
<mrow>& \equiv 271 \cdot 419 \cdot 16 \pmod{ 481}</mrow>
<mrow>& \equiv \mbox{1,816,784} \pmod{ 481}</mrow>
<mrow>& \equiv 47 \pmod{ 481}</mrow>
</md>.</p>
</example>
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{.}\)
Remark 4.4.2. Sage.
View Source for remark
<remark>
<title>Sage</title>
<p>Sage support for cyclic groups is a little spotty <mdash/> but we can still make effective use of Sage and perhaps this situation could change soon.</p>
</remark>
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.
You have attempted of activities on this page.
