Test di Miller-Rabin

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

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 ai test di Fermat e di test di Solovay-Strassen.

Definizione[modifica | modifica sorgente]

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:

  1. scegliamo a caso un intero b_1, con 1<b_1<n, e calcoliamo M.C.D.(b_1, n);
  2. se M.C.D.(b_1, n) > 1, allora n non è primo, ed abbiamo finito;
  3. 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;
  4. 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;
  5. 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:

  1. scegliamo a caso un intero b_m, con 1<b_m<n, e calcoliamo M.C.D.(b_m, n);
  2. se M.C.D.(b_m, n) > 1, allora n non è primo, ed abbiamo finito;
  3. 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[modifica | modifica sorgente]

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)[1].

Note[modifica | modifica sorgente]

  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[modifica | modifica sorgente]

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