Test di Miller-Rabin: differenze tra le versioni

Versione delle 20:34, 7 mar 2009

Versione delle 12:37, 8 ago 2009

Riga 3:

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

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.

Questo e'è il test di primalita'primalità 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 22:

# se M.C.D.(b<math>_m</math>, n) = 1, calcoliamo b<math>_m^{t}</math> (mod n), e procediamo come nel primo test. In questo modo troviamo che p non è primo, oppure che n è pseudoprimo forte in base b<math>_m</math>.

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

===Problemi aperti===

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

Riga 36:

* [[Test di Lucas-Lehmer]]

* [[Test di Wilson]]

{{Portale|matematica}}