1
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\).