Test di Miller-Rabin: differenze tra le versioni

Versione delle 14:14, 7 giu 2023

Versione delle 12:45, 15 mar 2025

Riga 3:

==Definizione==

Sia ''n'' un numero intero positivo dispari e non [[Numero primo|primo]] (quindi dispari). I numeri positivi ''b'' < ''n'' tali che M.C.D.(''b'', ''n'') = 1, e tali che ''n'' sia uno [[Pseudoprimo forte|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 fissoFissato un intero dispari ''n'' > 1, lo possopossiamo scrivere come <math>n = 2^{s} * t + 1</math>, con ''s'' ≥ 0 e ''t'' dispari. Il test T<math>_1</math> si sintetizza nei seguenti:

# scegliamo a caso un intero ''b''<math>_1</math>, con 1<''b''<math>_1</math><''n'', e calcoliamo M.C.D.(''b''<math>_1</math>, ''n'');

# se M.C.D.(''b''<math>_1</math>, ''n'') > 1, allora ''n'' non è primo, ed abbiamo finito;

# se M.C.D.(''b''<math>_1</math>, ''n'') = 1, calcoliamo ''b''<math>_1^{t}</math> (mod ''n''). Se ''b''<math>_1^{t}</math> ≡ +1 (mod ''n'') oppure ''b''<math>_1^{t}</math> ≡ -1−1 (mod ''n''), ''n'' è primo oppure è pseudoprimo forte in base ''b''<math>_1</math>;

# se non vale che ''b''<math>_1^{t}</math> ≡ +1 (mod ''n'') oppure ''b''<math>_1^{t}</math> ≡ -1−1 (mod ''n''), calcoliamo ''b''<math>_1^{2t}</math> (mod ''n''). Se ''b''<math>_1^{2t}</math> ≡ -1−1 (mod ''n''), allora ''n'' è pseudoprimo forte in base ''b''<math>_1</math>;

# se non vale che ''b''<math>_1^{2t}</math> ≡ -1−1 (mod ''n''), passiamo a ''b''<math>_1^{4t}</math>, e a tutte le altre potenze di 2, moltiplicate per ''t''. Se tutti i ''b''<math>_1^{2^{r}*t}</math>, per ''r'' = 1, ..., ''s-'' − 1, non sono mai congrui a -1−1 modulo ''n'', allora <math>''n</math>'' non è un primo. Altrimenti ''n'' è uno pseudoprimo forte in base ''b''<math>_1</math>.

Per tutti gli altri test {T<math>_m</math>}<math>_m</math>, m∈''m'' ∈ <math>\mathbb{N} </math>, la definizione è analoga:

# scegliamo a caso un intero ''b''<math>_m</math>, con 1<''b''<math>_m</math><n, e calcoliamo M.C.D.(''b''<math>_m</math>, ''n'');

# se M.C.D.(''b''<math>_m</math>, ''n'') > 1, allora ''n'' non è primo, ed abbiamo finito;

# se M.C.D.(''b''<math>_m</math>, ''n'') = 1, calcoliamo ''b''<math>_m^{t}</math> (mod ''n''), e procediamo come nel primo test. In questo modo troviamo che ''n'' non è primo, oppure che ''n'' è pseudoprimo forte in base ''b''<math>_m</math>.

==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<math>_m</math>, sappiamo che la probabilità che n non sia primo e sia uno pseudoprimo forte in base ''b''<math>_m</math> è minore di 1/4, e, quindi, la probabilità che ''n'' non sia primo ma passi i test T<math>_1</math>, T<math>_2</math>, ... , T<math>_m</math> è minore di <math>\left(\frac{1}{4^{m}}\right)</math>, 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 <math>O((\log n)^4\log\log\log n)</math><ref>{{cita pubblicazione |cognome= Miller|nome= Gary |anno= 1976|titolo= Riemann's Hypothesis and Tests for Primality |rivista= J. Comput. System Sci.|volume= 13|numero= 3|pp= 300-317|lingua= inglese }} ([https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf PDF])</ref>.