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 stochastiques de Monte-Carlo, et repose sur deux propriétés assez élémentaires d'arithmétique :
static boolean témoin(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; // ? } } static boolean millerRabin(int n, int t) { for (int i=0; i<t; i++) { int a = irand(2, n-1); if (témoin(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 témoin et dans la boucle for de millerRabin() 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 millerRabin() est invoqué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, une invocation de témoin(a,n) a une probabilité 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é 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 : 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 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.