L'exponentiation modulaire

def puissance_mod(a: int, n: int, p: int) -> int:
    r, b, m = 1, a % p, n
    while m > 0:
        # Invariant : (r * b**m) % p == (a**n) % p
        if m % 2 == 1:
            r = (r * b) % p
        b = (b * b) % p
        m = m // 2
    return r

Si l'on attendait la fin du calcul pour appliquer le modulo, les variables stockeraient des nombres géants (par exemple, $7^{2025}$ a plus de 1700 chiffres décimaux), ralentissant les multiplications et saturant la mémoire. Appliquer le modulo à chaque étape garantit que les variables manipulées restent inférieures à $p^2$.