|
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 al [[test di Fermat]] e al [[test di Solovay-Strassen]].
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<math>_m</math>}<math>_m</math>, m∈<math>\mathbb{N} </math>, finita o infinita, per i quali esiste una successione {δ<math>_m</math>}<math>_m</math>, m∈<math>\mathbb{N} </math> convergente a 0 di numeri reali positivi minori di 1, tale che se un numero intero positivo k non passa uno dei test T<math>_m</math> allora k non è di certo primo, mentre la probabilità che un numero intero positivo k passi i test T<math>_1</math>, T<math>_2</math>, ... , T<math>_m</math> e non sia primo è minore di δ<math>_m</math>. <br/>
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? <br/>
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.
==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 p<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'[[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>.
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]].
==Problemi apertiNote ==
<references/>
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 <math>O(\log n^{5})</math>.
== Voci correlate ==
* [[Test di Lucas-Lehmer]]
* [[Test di Wilson]]
== Altri progetti ==
{{Interprogetto|preposizione=sul}}
== Collegamenti esterni ==
* {{Collegamenti esterni}}
{{Portale|matematica}}
[[Categoria:Test di primalità]]
[[caCategoria:Test dedi primalitat de Miller-Rabinprimalità]]
[[de:Miller-Rabin-Test]]
[[en:Miller–Rabin primality test]]
[[es:Test de primalidad de Miller-Rabin]]
[[fr:Test de primalité de Miller-Rabin]]
[[he:אלגוריתם מילר-רבין]]
[[ja:ミラー-ラビン素数判定法]]
[[ko:밀러-라빈 소수판별법]]
[[nl:Miller-Rabin-priemgetaltest]]
[[pl:Test Millera-Rabina]]
[[pt:Teste de primalidade de Miller-Rabin]]
[[ru:Тест Миллера — Рабина]]
[[vi:Kiểm tra Miller-Rabin]]
[[zh:米勒-拉宾检验]]
| 