Contoh 4.3.1.
Kita akan menghitung \(271^{321} \pmod{ 481}\text{.}\) Perhatikan bahwa
\begin{equation*}
321 = 2^0 +2^6 + 2^8;
\end{equation*}
jadi, menghitung \(271^{ 321} \pmod{ 481}\) sama dengan menghitung
\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*}
Jadi, cukup dihitung \(271^{ 2^i } \pmod{ 481}\) dengan \(i = 0, 6, 8\text{.}\) Sangat mudah dilihat bahwa
\begin{equation*}
271^{ 2^1} = 73{,}441 \equiv 329 \pmod{ 481}\text{.}
\end{equation*}
Kita dapat menguadratkan hasil ini untuk memperoleh nilai \(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*}
Kita menggunakan fakta bahwa \((a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}\text{.}\) Dengan melanjutkan perhitungan, kita memperoleh
\begin{equation*}
271^{ 2^6 } \equiv 419 \pmod{481}
\end{equation*}
dan
\begin{equation*}
271^{ 2^8 } \equiv 16 \pmod{481}\text{.}
\end{equation*}
Oleh karena itu,
\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*}
