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 ${\displaystyle n}$  un numero intero positivo non primo (quindi dispari). I numeri positivi ${\displaystyle b<n}$  tali che ${\displaystyle \mathrm {MCD} (b,n)=1}$  e tali che ${\displaystyle n}$  sia uno pseudoprimo di Eulero forte in base ${\displaystyle b}$  sono non più di un quarto di tutti i numeri positivi ${\displaystyle b<n}$  tali che ${\displaystyle \mathrm {MCD} (b,n)=1.}$ 

Questo è il test di primalità che stavamo presentando:

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

1. scegliamo a caso un intero ${\displaystyle b_{1},}$  con ${\displaystyle 1<b_{1}<n,}$  e calcoliamo ${\displaystyle \mathrm {MCD} (b_{1},n);}$ 
2. se ${\displaystyle \mathrm {MCD} (b_{1},n)>1,}$  allora ${\displaystyle n}$  non è primo, ed abbiamo finito;
3. se ${\displaystyle \mathrm {MCD} (b_{1},n)=1,}$  calcoliamo ${\displaystyle b_{1}^{t}{\pmod {n}}.}$  Se ${\displaystyle b_{1}^{t}\equiv \pm 1{\pmod {n}},}$  allora ${\displaystyle n}$  è primo oppure è pseudoprimo forte in base ${\displaystyle b_{1}}$ ;
4. se non vale che ${\displaystyle b_{1}^{t}\equiv \pm 1{\pmod {n}},}$  calcoliamo ${\displaystyle b_{1}^{2t}{\pmod {n}}.}$  Se ${\displaystyle b_{1}^{2t}\equiv -1{\pmod {n}},}$  allora ${\displaystyle n}$  è pseudoprimo forte in base ${\displaystyle b_{1}}$ ;
5. se non vale che ${\displaystyle b_{1}^{2t}\equiv -1{\pmod {n}},}$  passiamo a ${\displaystyle b_{1}^{4t}}$  e a tutte le altre potenze di 2 moltiplicate per ${\displaystyle t.}$  Se tutti i ${\displaystyle b_{1}^{2^{r}t}}$ , per ${\displaystyle r=1,\ldots ,s-1,}$  non sono mai congrui a ${\displaystyle -1}$  modulo ${\displaystyle n,}$  allora ${\displaystyle n}$  non è un primo. Altrimenti ${\displaystyle n}$  è uno pseudoprimo forte in base ${\displaystyle b_{1}}$ .

Per tutti gli altri test ${\displaystyle T_{m},}$  per ${\displaystyle m}$  intero positivo, la definizione è analoga:

1. scegliamo a caso un intero ${\displaystyle b_{m}}$ , con ${\displaystyle 1<b_{m}<n}$ , e calcoliamo ${\displaystyle \mathrm {MCD} (b_{m},n)}$ ;
2. se ${\displaystyle \mathrm {MCD} (b_{m},n)>1,}$  allora ${\displaystyle n}$  non è primo, ed abbiamo finito;
3. se ${\displaystyle \mathrm {MCD} (b_{m},n)=1,}$  calcoliamo ${\displaystyle b_{m}^{t}{\pmod {n}}}$  e procediamo come nel primo test. In questo modo troviamo che ${\displaystyle n}$  non è primo, oppure che ${\displaystyle n}$  è pseudoprimo forte in base ${\displaystyle 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 ${\displaystyle T_{m}}$ , sappiamo che la probabilità che n non sia primo e sia uno pseudoprimo forte in base ${\displaystyle b_{m}}$  è minore di 1/4, e, quindi, la probabilità che ${\displaystyle n}$  non sia primo ma passi i test ${\displaystyle T_{1}}$ , ${\displaystyle T_{2}}$ , ..., ${\displaystyle T_{m}}$  è minore di ${\displaystyle {\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 ${\displaystyle O((\log n)^{4}\log \log \log n)}$ ^[1].

Note

1. ^ (EN) Gary Miller, Riemann's Hypothesis and Tests for Primality, in J. Comput. System Sci., vol. 13, n. 3, 1976, pp. 300-317. (PDF)

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.  

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica