Test di Miller-Rabin: differenze tra le versioni

Versione delle 12:50, 30 giu 2015

Versione delle 13:05, 30 mag 2016

Riga 26:

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

Assumendo l'[[Ipotesi di Riemann generalizzata]], 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)^4\log\log\log n)</math><ref>{{cita pubblicazione |cognome= Miller|nome= Gary |anno= 1976|titolo= Riemann's Hypothesis and Tests for Primality |rivista= J. Comput. System Sci.|volume= 13|numero= 3|paginepp= 300-317 |lingua= inglese }} ([http://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf PDF])</ref>.

== Note ==