Exponentiation modulaire rapide

let rec puissance_mod x n m =
  if n = 0 then 1 mod m
  else
    let p = puissance_mod x (n / 2) m in
    let p2 = (p * p) mod m in
    if n mod 2 = 0 then p2
    else (p2 * x) mod m

Même schéma que l'exponentiation rapide, mais on réduit modulo m après chaque produit : les valeurs restent bornées par m, ce qui évite les dépassements de capacité même pour de très grands exposants. C'est le cœur des calculs en arithmétique modulaire (cryptographie). $\Theta (\log n)$ multiplications.