Test di Miller-Rabin: differenze tra le versioni

Versione delle 21:46, 1 lug 2007

Versione delle 21:58, 1 lug 2007

Riga 1:

Il '''test di primalità di Miller-Rabin''', contrariamente al [[testTest di Wilson|Wilson]], è 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 è monore 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.