Des nombres premiers à Monte-Carlo

Le dernier des préceptes de Descartes est un obstacle à la conception de certains algorithmes : il faut savoir renoncer à l'exhaustivité et accepter des résultats << presque >> sûrs.

L'un des meilleurs tests de primalité est celui de Miller et Rabin, publié en 1976. Il appartient à la catégorie des algorithmes probabilistes de Monte-Carlo, et repose sur deux propriétés assez élémentaires d'arithmétique :

• Si $n$ est premier et ne divise pas $a$, alors $a^{n-1} = 1 \mathop{\normalfont\mathrm{mod}}\nolimits n$ ; par conséquent, si $a^{n-1} \not= 1 \mathop{\normalfont\mathrm{mod}}\nolimits n$, avec $1<a<n$, alors $n$ est nécessairement composé (mais il y a une infinité d'entiers composés, dits de Carmichael, qui échappent à ce test, le plus petit étant 561)
• Si $n$ est premier, alors les racines carrées de 1 modulo $n$ sont 1 et $-1$ ; par conséquent, s'il existe une racine carrée de l'unité modulo $n$ non triviale (c'est-à-dire, s'il existe $r$ tel que $r^2 = 1 \mathop{\normalfont\mathrm{mod}}\nolimits n$, $r \not= 1 \mathop{\normalfont\mathrm{mod}}\nolimits n$ et $r \not=n-1 \mathop{\normalfont\mathrm{mod}}\nolimits n$), alors $n$ est composé.

Le principe de l'algorithme de Miller-Rabin est de tirer aléatoirement $a$ dans $[2,n-1]$ et de calculer $a^{n-1} \mathop{\normalfont\mathrm{mod}}\nolimits n$ au moyen de l'algorithme d'exponentiation rapide expmod_iter, qui a été vu au §23. Comme il procède par carrés successifs, ce dernier algorithme donne l'opportunité de découvrir au passage une racine carrée non-triviale de 1. Il suffit de modifier légèrement expmod_iter ; la fonction temoin qui en dérive retourne true dès qu'une racine carrée non-triviale est obtenue ou si $a^{n-1} \not= 1 \mathop{\normalfont\mathrm{mod}}\nolimits n$, ce qui permet de conclure que $n$ est composé ; on dit alors que $a$ est un témoin de Miller, c'est-à-dire une preuve, du fait que $n$ est composé ; elle retourne false sinon, ce qui est un indice de primalité, qui devra être confirmé ou infirmé par d'autres tirages aléatoires.

bool temoin(int a, int n) {
  int m = n-1;
  int y = 1;

  while (m != 0) {
    if (m%2 == 1) {
      y = (a*y) % n;
      m = m-1;
    } else {
      int b = a;

      a = (a*a) % n;
      if (a==1 && b!=1 && b!=n-1) {
        // b est une racine carre non triviale de 1
        return true;               // n est composé
      }
      m = m/2;
    }
  }
  if (y != 1) {
    return true;                   // n est composé
  } else {
    return false;                  // ? 
  }
}

bool Miller_Rabin(int n, int t) {
  int i;

  for (i=0; i<t; i++) {
    int a = irand(2, n-1);

    if (temoin(a,n)) {
      return true;                 // n est composé
    }
  }
  return false;                    // n est probablement premier
}

On notera que le << return true; >> placé dans la boucle while de temoin et dans la boucle for de Miller_Rabin permet de s'en échapper (c'est-à-dire de ne pas exécuter les itérations suivantes) en retournant immédiatement une valeur.

La fonction Miller_Rabin est appelée avec deux arguments, l'entier $n$ à tester et le nombre $t$ de tirages ; elle retourne true dès qu'un témoin est trouvé, auquel cas $n$ est composé, et false sinon, auquel cas $n$ est probablement premier.

Combien de tirages sont nécessaires ? On montre que si $n$ est composé et impair, au moins $3/4$ des $n-2$ entiers $a$ tels que $1<a<n$ sont des témoins de Miller pour $n$ ; donc quand $a$ est tiré aléatoirement avec une probabilité uniforme, un appel à temoin(a,n) a une probabilité $\ge 3/4$ de retourner 1, et une probabilité $< 1/4$ de retourner 0, c'est-à-dire de laisser croire que $n$ est premier. Les tirages étant indépendants, la fonction Miller_Rabin(n,t) a une probabilité $< (\frac{1}{4})^t$ de retourner 0 alors que $n$ est composé. Ainsi, la réponse << $n$ est composé >> est toujours exacte, et une réponse << $n$ est probablement premier >> est exacte avec une probabilité d'erreur $< (\frac{1}{4})^t$ : l'obstination permet de réduire la probabilité d'erreur à un nombre aussi petit qu'on le souhaite. Quel que soit $n$, 50 tirages suffisent largement (la probabilité d'erreur est alors de l'ordre de $10^{-31}$). Abelson[1] fait remarquer qu'on obtient ainsi une probabilité inférieure à la probabilité d'une erreur à l'exécution due à à l'incidence d'une radiation cosmique sur la machine ; et il ajoute << juger de l'adéquation d'un algorithme en prenant en compte le premier type d'erreur mais pas le second illustre la différence entre un mathématicien et un ingénieur >>.

L'algorithme de Miller-Rabin a une complexité en $O(t \log n)$ opérations. Aucun algorithme déterministe n'est en revanche capable de résoudre le problème de primalité en un temps raisonnable pour des entiers à plusieurs centaines de chiffres. Ce problème est pourtant important pour garantir la sécurité des systèmes de chiffrement, donc finalement la sécurité de nombre d'applications informatiques ainsi que la confidentialité des données. Le problème de factorisation des grands entiers est encore plus difficile et encore plus crucial pour la sécurité ; aucun algorithme, ni déterministe, ni de Monte-Carlo ne parvient à le résoudre.