Test di Miller-Rabin: differenze tra le versioni

Versione delle 12:13, 28 giu 2007

Versione delle 12:15, 28 giu 2007

Riga 1:

Il '''test di primalità di Miller-Rabin''', contrariamente ai [[test di Fermat e 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 guadagnamo 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 33:

* [[Test di Lucas - Lehmer]]

* [[Test di Wilson]]

[[de:Miller-Rabin-Test]]

[[en:Miller-Rabin primality test]]

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

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

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

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

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

[[pl:Test Millera-Rabina]]

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

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

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

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