Test di Miller-Rabin: differenze tra le versioni

Versione delle 21:35, 1 lug 2007

Versione delle 21:36, 1 lug 2007

Riga 24:

===Considerazioni finali sul test===

Si può subito notare che, a differenza dei test[[Test di WilsonFermat]] e Fermat[[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.