Exemple 4.3.1.
Nous allons calculer \(271^{321} \pmod{ 481}\text{.}\) Remarquons que
\begin{equation*}
321 = 2^0 +2^6 + 2^8;
\end{equation*}
donc, calculer \(271^{ 321} \pmod{ 481}\) est la même chose que calculer
\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*}
Il suffira donc de calculer \(271^{ 2^i } \pmod{ 481}\) pour \(i = 0, 6, 8\text{.}\) Il est très facile de voir que
\begin{equation*}
271^{ 2^1} = 73{,}441 \equiv 329 \pmod{ 481}\text{.}
\end{equation*}
Nous pouvons élever ce résultat au carré pour obtenir une valeur pour \(271^{ 2^2} \pmod{481}\) :
\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*}
Nous utilisons le fait que \((a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}\text{.}\) En continuant, nous pouvons calculer
\begin{equation*}
271^{ 2^6 } \equiv 419 \pmod{481}
\end{equation*}
et
\begin{equation*}
271^{ 2^8 } \equiv 16 \pmod{481}\text{.}
\end{equation*}
Par conséquent,
\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*}
