exo7 7307

Il est souvent important de calculer $a^t$ modulo $n$ avec $a, t, n$ grands (calculer $a^t$ dans $\Z$ n’est pas envisageable). Méthode : Ecrire $t$ en binaire : $t =\Sigma t_i2^i$ (où $t^i\in\{0, 1\}$). Les $a^{2^i}$ se calculent facilement par élévations au carré successives modulo $n$, et $a^t$ modulo $n$ est le produit (modulo $n$) des $a^{2^i}$ pour lesquels $t^i = 1$.

Calculer $3^{2025}$ modulo $50$.