Exponentielle modulaire

La fonction exponentielle croissant très rapidement, on dépasse facilement les limites de l'arithmétique entière de la machine, et on ne profite guère de cette accélération. Calculons plutôt $x^e \mathop{\normalfont\mathrm{mod}}\nolimits m$, de façon à rester dans ces limites. Il suffit de placer un %m après chaque opération. Voici la version récursive terminale de cette fonction :

int expmod_fastrec_aux(int x, int y, int e, int m) {
  if (e == 0) {
    return y;
  } else if (e % 2 == 1) {
    return expmod_fastrec_aux(x, (x*y) % m, e-1, m);
  } else {
    return expmod_fastrec_aux((x*x) % m, y, e/2, m);
  }
}

int expmod_fastrec(int x, int e, int m) {
  return expmod_fastrec_aux(x, 1, e, m);
}

La version itérative s'obtient facilement par dérécursivation de cette définition récursive terminale :

int expmod_iter(int x, int e, int m) {
  int y = 1;

  while (e != 0) {
    if (e%2 == 1) {
      y = (x*y) % m;
      e = e-1;
    } else {
      x = (x*x) % m;
      e = e/2;
    }
  }
  return y;
}

L'exponentielle modulaire s'avère utile à certaines méthodes de cryptographie.