Test de primalité de Miller-Rabin
Soit $n$ un nombre premier impair que l'on décompose sous la forme $n=2^s\times d+1$. Alors $n$ a la propriété suivante : pour tout entier $a$ compris entre $1$ et $n-1$, alors
- ou bien $a^d\equiv 1\ [n]$ ;
- ou bien il existe $i$ dans $\{1,…,s-1\}$ tel que $a^{2^id}\equiv -1\ [n]$.
On peut en déduire un test probabiliste de primalité d'un entier. Prenons maintenant $n$ impair quelconque, qu'on écrit $n=2^s\times d+1$, et $a$ toujours compris entre $1$ et $n-1$. Si
- ou bien $a^d\equiv 1\ [n]$
- ou bien il existe $i$ dans $\{1,…,s-1\}$ tel que $a^{2^id}\equiv -1\ [n]$
on dit que $n$ passe le test. Un entier premier $n$ va passer le test pour tout entier $a$. Toutefois, pour un $a$ fixé, un entier non premier $n$ peut aussi passer le test. On démontre qu'il ne peut pas le passer pour plus d'un quart des entiers $a$ compris entre $1$ et $n-1$. En répétant le test avec plusieurs entiers $a$ différents, on pourra donc affirmer, s'il passe les différents tests, que $n$ est probablement premier.