Test di Miller-Rabin: differenze tra le versioni

Versione delle 16:04, 13 set 2007

Versione attuale delle 16:10, 15 mar 2025

(35 versioni intermedie di 27 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 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>

Questo e'è il test di primalita'primalità che stavamo presentando:

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.

Fissato un intero dispari <math>n>1,</math> lo possiamo scrivere come <math>n = 2^s t + 1</math>, con <math>s\ge 0</math> e <math>t</math> dispari. Il test <math>T_1</math> si sintetizza nei seguenti:

Questo e' il test di primalita' che stavamo presentando:

# 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>.

SePer fissotutti ungli interoaltri disparitest n>1, lo posso scrivere come n=2<math>^{s}T_m,</math>*t+1, conper t dispari. Il test T<math>_1m</math> siintero positivo, la sintetizzadefinizione neiè seguentianaloga:

# 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 (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 (mod n), calcoliamo b<math>_1^{2t}</math> (mod n). Se b<math>_1^{2t}</math> ≡ -1 (mod n), allora n è pseudoprimo forte in base b<math>_1</math>;

# se non vale che b<math>_1^{2t}</math> ≡ -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 modulo n, allora <math>n</math> non è un primo. Altrimenti n è uno pseudoprimo forte in base b<math>_1</math>.

Per# tuttiscegliamo glia altricaso testun intero {T<math>_mb_m</math>}, con <math>_m1<b_m<n</math>, m∈e calcoliamo <math>\mathbbmathrm{NMCD} (b_m,n)</math>, la definizione è analoga:;

# 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===

# 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);

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]].

# 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 p non è primo, oppure che n è pseudoprimo forte in base b<math>_m</math>.

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>.

===Considerazioni finali sul test===

== Note ==

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.

<references/>

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]].

== Voci correlate ==

Riga 34:

* [[Test di Wilson]]

== Altri progetti ==

[[Categoria:Test di primalità]]

{{Interprogetto|preposizione=sul}}

== Collegamenti esterni ==

[[de:Miller-Rabin-Test]]

* {{Collegamenti esterni}}

[[en:Miller-Rabin primality test]]

[[es:Test de primalidad de Miller-Rabin]]

{{Portale|matematica}}

[[fr:Test de primalité de Miller-Rabin]]

[[ko:밀러-라빈 소수판별법]]

[[Categoria:Test di primalità]]

[[he:אלגוריתם מילר-רבין]]

[[ja:ミラー-ラビン素数判定法]]

[[pl:Test Millera-Rabina]]

[[pt:Teste de primitividade de Miller-Rabin]]

[[ru:Тест Миллера — Рабина]]

[[vi:Kiểm tra Miller-Rabin]]

[[zh:米勒-拉宾检验]]