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 :
; par conséquent, si 
, 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)
, 
et 
), alors n est
composé.
au moyen de
l'algorithme d'exponentiation rapide expmod_iter, qui a été vu
au §
. 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 1 dès qu'une racine carrée non-triviale est obtenue ou si
, 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 0 sinon, ce qui est
un indice de primalité, qui devra être confirmé ou infirmé par d'autres
tirages aléatoires.
int 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 1;
}
m = m/2;
}
}
if (y != 1) {
return 1;
} else {
return 0;
}
}
int 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 1;
}
}
return 0;
}
On notera que le << return 1; >> 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 1 dès qu'un témoin est trouvé, auquel cas n est composé, et 0 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é 
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 
).
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, et dans
les pays qui le permettent, 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.