Test di Miller-Rabin: differenze tra le versioni

Versione delle 16:04, 13 set 2007

Versione delle 18:07, 15 set 2007

Riga 26:

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]] estesa (ERH) è vera, il test di Miller-Rabin diventa un test di primalità e se ne può ricavare un algoritmo con costo <math>O(\log n^{5})</math>

== Voci correlate ==