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 non primo (quindi dispari). I numeri positivi $b<n$ tali che $\mathrm {MCD} (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 $\mathrm {MCD} (b,n)=1.$

Questo è il test di primalità che stavamo presentando:

Fissato un intero dispari $n>1,$ lo possiamo scrivere come $n=2^{s}t+1$, con $s\geq 0$ e $t$ dispari. Il test $T_{1}$ si sintetizza nei seguenti:

1. scegliamo a caso un intero $b_{1},$ con $1<b_{1}<n,$ e calcoliamo $\mathrm {MCD} (b_{1},n);$
2. se $\mathrm {MCD} (b_{1},n)>1,$ allora $n$ non è primo, ed abbiamo finito;
3. se $\mathrm {MCD} (b_{1},n)=1,$ calcoliamo $b_{1}^{t}{\pmod {n}}.$ Se $b_{1}^{t}\equiv \pm 1{\pmod {n}},$ allora $n$ è primo oppure è pseudoprimo forte in base $b_{1}$;
4. se non vale che $b_{1}^{t}\equiv \pm 1{\pmod {n}},$ calcoliamo $b_{1}^{2t}{\pmod {n}}.$ Se $b_{1}^{2t}\equiv -1{\pmod {n}},$ allora $n$ è pseudoprimo forte in base $b_{1}$;
5. se non vale che $b_{1}^{2t}\equiv -1{\pmod {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,\ldots ,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},$ per $m$ intero positivo, la definizione è analoga:

1. scegliamo a caso un intero $b_{m}$, con $1<b_{m}<n$, e calcoliamo $\mathrm {MCD} (b_{m},n)$;
2. se $\mathrm {MCD} (b_{m},n)>1,$ allora $n$ non è primo, ed abbiamo finito;
3. se $\mathrm {MCD} (b_{m},n)=1,$ calcoliamo $b_{m}^{t}{\pmod {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 ${\frac {1}{4^{m}}}$, 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)$.

Voci correlate

• Numero primo
• Pseudoprimo
• Test di Fermat
• Test di Lucas-Lehmer
• Test di Wilson

Altri progetti

Altri progetti

• Wikibooks

• Wikibooks contiene testi o manuali sul Test di Miller-Rabin

Collegamenti esterni

• (EN) Miller-Rabin test, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Rabin-Miller Strong Pseudoprime Test, su MathWorld, Wolfram Research.