Test di Miller-Rabin: differenze tra le versioni

Versione delle 00:30, 29 dic 2009

Versione delle 03:10, 13 gen 2010

Riga 1:

{{Avvisounicode}}

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