Sia $Random(1, n-1)$ un algoritmo che restituisce un numero $a$ compreso tra $1$ ed $n-1$ scelto in modo casuale, sia $Witness(a,n)$ un algoritmo che restituisce $true$ se e solo se il valore $a$ è un testimone della compostezza di $n$

Quindi

• se $Witness(a,n)$ restituisce $true$ alla fine allora $a^{n-1} \neq 1$ $\text{mod}$ $n$ → per il teorema di Fermat $n$ non può essere primo ed $a$ è una prova della sua compostezza
• se $Witness(a,n)$ restituisce $true$ nel primo caso allora ha individuato una radice quadrata $x$ non banale di $1$ $\text{mod}$ $n$ → $n$ è composto

La procedura di Miller e Rabin è una ricerca probabilistica parametrizzata di una prova che $n$ è composto

Sceglie $s$ valori casuali e se una di queste scelte risulta essere un testimone che $n$ è composto allora la procedura restituisce composto

D’altra parte se nessun testimone viene trovato negli $s$ tentativi assume che ciò accada perché non ci sono testimoni e di conseguenza restituisce primo

Infatti se $n$ è primo l’equazione $a^{n-1} \equiv 1$ $\text{mod}$ $n$ è soddisfatta per ogni $a$ e le radici quadrate di $1$ $\text{mod}$ $n$ sono solo $\pm1$

Se il valore del parametro $s$ viene scelto sufficientemente grande, è molto probabile che il risultato sia corretto, ma c’è una piccola probabilità che la procedura sia stata sfortunata nelle scelte casuali delle $a$ e che qualche testimone esista ma non sia stato trovato

Teorema dei testimoni

Se $n$ è un intero dispari composto allora il numero di testimoni della sua compostezza è almeno $\frac{n-1}2$

Teorema

Per ogni intero dispari $n >2$ ed ogni intero positivo $s$, la probabilità che il test di Miller e Rabin sbagli è al più $2^{-s}$