Test di Miller-Rabin: differenze tra le versioni

Versione delle 12:22, 11 mar 2013

Versione attuale delle 16:10, 15 mar 2025

(13 versioni intermedie di 12 utenti non mostrate)

Riga 1:

Il '''test di primalità di Miller-Rabin''' è un [[test di primalità]], ossia un [[algoritmo]] per determinare se un [[numero intero]] è [[numero primo|primo]]. La sua versione originale, dovuta a [[Gary Miller (informatico)|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 [[algoritmo probabilistico|probabilistica]] simile aial [[test di Fermat]] e dial [[test di Solovay-Strassen]].

{{Avvisounicode}}

Il '''test di primalità di Miller-Rabin''' è un [[test di primalità]], ossia un [[algoritmo]] per determinare se un [[numero intero]] è [[numero primo|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 [[algoritmo probabilistico|probabilistica]] simile ai [[test di Fermat]] e di [[test di Solovay-Strassen]].

==Definizione==

==Test di primalità di Miller-Rabin==

Sia <math>n</math> un numero intero positivo dispari e non [[Numero primo|primo]] (quindi dispari). I numeri positivi <math>b<n</math> tali che M.C.D.<math>\mathrm{MCD}(b,n) = 1,</math> e tali che <math>n</math> sia uno [[Pseudoprimo forte|pseudoprimo di Eulero forte]] in base <math>b</math> sono non più di un quarto di tutti i numeri positivi <math>b<n</math> tali che M.C.D.<math>\mathrm{MCD}(b,n) = 1.</math>

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 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 <math>n>1,</math> lo possopossiamo scrivere come n=2<math>n = 2^{s} t + 1</math>*t+1, con <math>s\ge 0</math> e <math>t</math> dispari. Il test T<math>_1T_1</math> si sintetizza nei seguenti:

# scegliamo a caso un intero b<math>_1b_1,</math>, con 1<b<math>_11<b_1<n,</math><n, e calcoliamo M.C.D.(b<math>_1\mathrm{MCD}(b_1,n);</math>, n);

# se M.C.D.(b<math>_1</math>\mathrm{MCD}(b_1, n) > 1,</math> allora <math>n</math> non è primo, ed abbiamo finito;

# se M.C.D.(b<math>_1</math>\mathrm{MCD}(b_1, n) = 1,</math> calcoliamo b<math>_1b_1^{t}\pmod n.</math> (mod n). Se b<math>_1b_1^{t}</math>\equiv ≡\pm +1 (mod\pmod n),</math> oppureallora b<math>_1^{t}n</math> ≡ -1 (mod n), n è primo oppure è pseudoprimo forte in base b<math>_1b_1</math>;

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

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

Per tutti gli altri test {T<math>_mT_m,</math>} per <math>_mm</math>, m∈<math>\mathbb{N}intero </math>positivo, la definizione è analoga:

# scegliamo a caso un intero b<math>_mb_m</math>, con 1<b<math>_m1<b_m<n</math><n, e calcoliamo M.C.D.(b<math>_m\mathrm{MCD}(b_m,n)</math>, n);

# se M.C.D.(b<math>_m</math>\mathrm{MCD}(b_m, n) > 1,</math> allora <math>n</math> non è primo, ed abbiamo finito;

# se M.C.D.(b<math>_m</math>\mathrm{MCD}(b_m, n) = 1,</math> calcoliamo b<math>_mb_m^{t}\pmod n</math> (mod n), e procediamo come nel primo test. In questo modo troviamo che <math>n</math> non è primo, oppure che <math>n</math> è pseudoprimo forte in base b<math>_mb_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>_mT_m</math>, sappiamo che la probabilità che n non sia primo e sia uno pseudoprimo forte in base b<math>_mb_m</math> è minore di 1/4, e, quindi, la probabilità che <math>n</math> non sia primo ma passi i test T<math>_1T_1</math>, T<math>_2T_2</math>, ... , T<math>_mT_m</math> è minore di <math>\left(\frac{1}{4^{m}}\right)</math>, ossia piccolissima rispetto a quella del [[Testtest di Fermat]].

Assumendo l'[[Ipotesiipotesi 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|mese= |titolo= Riemann's Hypothesis and Tests for Primality |rivista= J. Comput. System Sci.|volume= 13|numero= 3|paginepp= 300-317 |lingua= inglese }} ([httphttps://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf PDF])</ref>.

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|mese= |titolo= Riemann's Hypothesis and Tests for Primality |rivista= J. Comput. System Sci.|volume= 13|numero= 3|pagine= 300-317 |lingua= inglese }} ([http://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf PDF])</ref>.

== Note ==

Riga 37 ⟶ 33:

* [[Test di Lucas-Lehmer]]

* [[Test di Wilson]]

== Altri progetti ==

{{Interprogetto|preposizione=sul}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Test di primalità]]