Test di Miller-Rabin
# Test di Miller-Rabin

Il test di primalità di Miller-Rabin è un test di primalità, ossia un algoritmo per determinare se un numero intero è primo. La sua versione originale, dovuta a Gary Miller, è deterministica, ma dipende dall'ipotesi di Riemann generalizzata, un'importante congettura matematica tuttora aperta. L'algoritmo è stato successivamente modificato da Michael Rabin che ne ha ottenuto una versione probabilistica simile al test di Fermat e al test di Solovay-Strassen.

## Definizione

Sia n un numero intero positivo dispari e non primo. I numeri positivi b<n tali che M.C.D.(b,n)=1, e tali che n sia uno pseudoprimo di Eulero forte in base b sono non più di un quarto di tutti i numeri positivi b<n tali che M.C.D.(b,n)=1.

Questo è il test di primalità che stavamo presentando:

Se fisso un intero dispari n>1, lo posso scrivere come $n=2^{s}*t+1$, con t dispari. Il test $T_{1}$ si sintetizza nei seguenti:

* scegliamo a caso un intero $b_{1},$ con $1<b_{1}<n,$ e calcoliamo $M.C.D.(b_{1},$ n);
* se $M.C.D.(b_{1},$ n) > 1, allora n non è primo, ed abbiamo finito;
* se $M.C.D.(b_{1},$ n) = 1, calcoliamo b$_{1}^{t}$ (mod n). Se b$_{1}^{t}$ ≡ +1 (mod n) oppure b$_{1}^{t}$ ≡ -1 (mod n), n è primo oppure è pseudoprimo forte in base $b_{1};$
* se non vale che b$_{1}^{t}$ ≡ +1 (mod n) oppure b$_{1}^{t}$ ≡ -1 (mod n), calcoliamo b$_{1}^{2t}$ (mod n). Se b$_{1}^{2t}$ ≡ -1 (mod n), allora n è pseudoprimo forte in base $b_{1};$
* se non vale che b$_{1}^{2t}$ ≡ -1 (mod n), passiamo a b$_{1}^{4t}$, e a tutte le altre potenze di 2, moltiplicate per t. Se tutti i b$_{1}^{2^{r}*t}$, per r=1,..., s-1, non sono mai congrui a -1 modulo n, allora $n$ non è un primo. Altrimenti n è uno pseudoprimo forte in base $b_{1}.$

Per tutti gli altri test ${T_{m}}_{m},$ m∈$\mathbb {N}$, la definizione è analoga:

* scegliamo a caso un intero $b_{m},$ con $1<b_{m}<n,$ e calcoliamo $M.C.D.(b_{m},$ n);
* se $M.C.D.(b_{m},$ n) > 1, allora n non è primo, ed abbiamo finito;
* se $M.C.D.(b_{m},$ n) = 1, calcoliamo b$_{m}^{t}$ (mod n), e procediamo come nel primo test. In questo modo troviamo che n non è primo, oppure che n è pseudoprimo forte in base $b_{m}.$

## Considerazioni finali sul test

Si può subito notare che, a differenza dei Test di Fermat e Test di Wilson, qui i calcoli sono minori in numero e molto più semplici, e si può dimostrare che il livello di complessità computazionale è polinomiale, mentre gli altri due presentano una difficoltà computazionale esponenziale. Per quanto riguarda l'affidabilità, anch'essa è molto buona in questo test. Infatti, nonostante sia un test probabilistico, quando effettuiamo il test $T_{m},$ sappiamo che la probabilità che n non sia primo e sia uno pseudoprimo forte in base $b_{m}$ è minore di 1/4, e, quindi, la probabilità che n non sia primo ma passi i test $T_{1},$ $T_{2},$ ... , $T_{m}$ è minore di $\left({\frac {1}{4^{m}}}\right)$, ossia piccolissima rispetto a quella del Test di Fermat.

Assumendo l'Ipotesi di Riemann generalizzata, il test di Miller-Rabin si può facilmente modificare in modo da diventare un vero test di primalità e l'algoritmo ad esso associato avrebbe costo $O((\log n)^{4}\log \log \log n)$.

