Prépa Code Connexion Inscription

Écrire une fonction récursive expo_mod : int -> int -> int -> int telle que expo_mod a n m renvoie $a^n \bmod m$, en utilisant le principe de l'exponentiation rapide pour s'exécuter en $O(\log n)$ multiplications.

On suppose n >= 0 et m > 0. On ne cherche pas à gérer les très grands nombres : la seule contrainte est d'avoir une complexité logarithmique.

Par convention, expo_mod a 0 m = 1 mod m.