Miller-Rabin

On choisit au hasard 20 nombres $a$ pour faire subir à $N$ l'algorithme général. Si pour tout $a$ l'algorithme répond ``N est premier'' alors la probabilité d'erreur est de $1/4^{20}\; (\simeq 10^{-12})$ . Cette marge d'erreur (quasi nulle, voire nulle) fait que l'on appelle de tels $N$ des premiers industriels ^2.2 (par opposition aux vrais nombres premiers, prouvés premiers par les tests de la section suivante).

D'autre part, s'il existe un $a$ tel que l'algorithme général réponde ``N n'est pas premier'', alors il est certain que $N$ est composé.

Ce test ne donne donc absolument pas de preuve que $N$ est premier.