Test di Miller-Rabin: differenze tra le versioni

Versione delle 02:15, 6 dic 2011

Versione delle 03:24, 6 dic 2011

Riga 1:

{{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'algoritomo è 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]].

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.

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

Riga 28 ⟶ 26:

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

{{Citazione necessaria|SeAssumendo 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^{54+\varepsilon}),</math> per ogni &epsilon;>0.<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 }}</ref>

==Problemi aperti==

{{Citazione necessaria|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>.}}

== Note ==

<references/>

== Voci correlate ==