Test di Miller-Rabin: differenze tra le versioni

Versione delle 00:56, 10 ago 2007

Versione delle 16:29, 7 set 2007

Riga 1:

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.

Riga 7:

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.

InQuesto basee' ail questatest proposizionedi possiamo mostrare il testprimalita' che stavamo presentando.:

Se fisso un intero dispari n>1, lo posso scrivere come n=2<math>^{s}</math>*t+1, con t dispari. Il test T<math>_1</math> si sintetizza nei seguenti:

Riga 24:

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

== Voci correlate ==