Example4.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}.
\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} = \text{73,441} \equiv 329 \pmod{ 481}.
\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 \text{108,241} \pmod{ 481}\\
& \equiv 16 \pmod{ 481}.
\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}.
\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 \text{1,816,784} \pmod{ 481}\\
& \equiv 47 \pmod{ 481}.
\end{align*}