Test di Miller-Rabin

Il test di primalità di Miller-Rabin, contrariamente al Test di Wilson e similmente al Test di Fermat, è un test di tipo probabilistico, ossia esso consiste in una successione di test {T${\displaystyle _{m}}$}${\displaystyle _{m}}$, m∈${\displaystyle \mathbb {N} }$, finita o infinita, per i quali esiste una successione {δ${\displaystyle _{m}}$}${\displaystyle _{m}}$, m∈${\displaystyle \mathbb {N} }$ convergente a 0 di numeri reali positivi minori di 1, tale che se un numero intero positivo k non passa uno dei test T${\displaystyle _{m}}$ allora k non è di certo primo, mentre la probabilità che un numero intero positivo k passi i test T${\displaystyle _{1}}$, T${\displaystyle _{2}}$, ... , T${\displaystyle _{m}}$ e non sia primo è minore di δ${\displaystyle _{m}}$.
Che cosa guadagniamo utilizzando i test probabilistici, rispetto a quelli deterministici, considerando, comunque, che i primi non danno una risposta certa per ogni intero k considerato?
Di solito, i test probabilistici ci forniscono un metodo molto più semplice e meno gravoso dal punto di vista computazionale, con grossi risparmi di tempo; è proprio per questo motivo che, per valutare interi positivi k molto molto grandi, di solito si preferisce un test probabilistico ad uno deterministico.

Test di primalità di Miller-Rabin

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${\displaystyle ^{s}}$ *t+1, con t dispari. Il test T${\displaystyle _{1}}$  si sintetizza nei seguenti:

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

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

1. scegliamo a caso un intero b${\displaystyle _{m}}$ , con 1<b${\displaystyle _{m}}$ <n, e calcoliamo M.C.D.(b${\displaystyle _{m}}$ , n);
2. se M.C.D.(b${\displaystyle _{m}}$ , n) > 1, allora n non è primo, ed abbiamo finito;
3. se M.C.D.(b${\displaystyle _{m}}$ , n) = 1, calcoliamo b${\displaystyle _{m}^{t}}$  (mod n), e procediamo come nel primo test. In questo modo troviamo che p non è primo, oppure che n è pseudoprimo forte in base b${\displaystyle _{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${\displaystyle _{m}}$ , sappiamo che la probabilità che n non sia primo e sia uno pseudoprimo forte in base b${\displaystyle _{m}}$  è minore di 1/4, e, quindi, la probabilità che n non sia primo ma passi i test T${\displaystyle _{1}}$ , T${\displaystyle _{2}}$ , ... , T${\displaystyle _{m}}$  è minore di ${\displaystyle \left({\frac {1}{4^{m}}}\right)}$ , ossia piccolissima rispetto a quella del Test di Fermat.

Problemi aperti

Se l'Ipotesi di Riemann generalizzata è vera, 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^{5})}$ .

Voci correlate

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

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