Example 4.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}\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} = 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 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 1{,}816{,}784 \pmod{ 481}\\
& \equiv 47 \pmod{ 481}\text{.}
\end{align*}
