|
==Definizione==
Sia ''<math>n ''</math> un numero intero positivo non [[Numero primo|primo]] (quindi dispari). I numeri positivi ''<math>b '' < ''n ''</math> tali che M.C.D.<math>\mathrm{MCD}( ''b '', ''n '') = 1 </math> e tali che ''<math>n ''</math> sia uno [[Pseudoprimo forte|pseudoprimo di Eulero forte]] in base ''<math>b ''</math> sono non più di un quarto di tutti i numeri positivi ''<math>b '' < ''n ''</math> tali che M.C.D.<math>\mathrm{MCD}( ''b '', ''n '') = 1. </math>▼
▲Sia ''n'' un numero intero positivo non [[Numero primo|primo]] (quindi dispari). I numeri positivi ''b'' < ''n'' tali che M.C.D.(''b'', ''n'') = 1 e tali che ''n'' sia uno [[Pseudoprimo forte|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 è il test di primalità che stavamo presentando:
Fissato un intero dispari ''<math>n'' > 1,</math> lo possiamo scrivere come <math>n = 2^s t + 1</math>, con ''<math>s'' ≥\ge 0</math> e ''<math>t''</math> dispari. Il test T<math>_1T_1</math> si sintetizza nei seguenti:
# scegliamo a caso un intero ''b''<math>_1b_1,</math>, con 1<''b''<math>_11<b_1<n,</math><''n'', e calcoliamo M.C.D.(''b''<math>_1\mathrm{MCD}(b_1,n);</math>, ''n'');
# se M.C.D.(''b''<math>_1</math>\mathrm{MCD}(b_1, ''n'') > 1,</math> allora ''<math>n''</math> non è primo, ed abbiamo finito;
# se M.C.D.(''b''<math>_1</math>\mathrm{MCD}(b_1, ''n'') = 1,</math> calcoliamo ''b''<math>_1b_1^{t}\pmod n.</math> (mod ''n''). Se ''b''<math>_1b_1^{t}</math>\equiv ≡\pm +1\pmod (mod ''n''),</math> oppureallora ''b''<math>_1^{t}n</math> ≡ −1 (mod ''n''), ''n'' è primo oppure è pseudoprimo forte in base ''b''<math>_1b_1</math>;
# se non vale che ''b''<math>_1b_1^{t}</math>\equiv ≡\pm +1\pmod (mod ''n'') oppure ''b''<math>_1^{t},</math> ≡ −1 (mod ''n''), calcoliamo ''b''<math>_1b_1^{2t}\pmod n.</math> (mod ''n''). Se ''b''<math>_1b_1^{2t}\equiv -1\pmod n,</math> ≡ −1 (mod ''n''), allora ''<math>n''</math> è pseudoprimo forte in base ''b''<math>_1b_1</math>;
# se non vale che ''b''<math>_1b_1^{2t}\equiv -1\pmod n,</math> ≡ −1 (mod ''n''), passiamo a ''b''<math>_1b_1^{4t}</math>, e a tutte le altre potenze di 2, moltiplicate per ''<math>t''.</math> Se tutti i ''b''<math>_1b_1^{2^{r}t}</math>, per ''<math>r'' = 1, ...\ldots, ''s'' − -1,</math> non sono mai congrui a −1<math>-1</math> modulo ''<math>n'',</math> allora ''<math>n''</math> non è un primo. Altrimenti ''<math>n''</math> è uno pseudoprimo forte in base ''b''<math>_1b_1</math>.
Per tutti gli altri test {T<math>_mT_m,</math>} per <math>_mm</math>, ''m''intero ∈ <math>\mathbb{N} </math>positivo, la definizione è analoga:
# scegliamo a caso un intero ''b''<math>_mb_m</math>, con 1<''b''<math>_m1<b_m<n</math><n, e calcoliamo M.C.D.(''b''<math>_m\mathrm{MCD}(b_m,n)</math>, ''n'');
# se M.C.D.(''b''<math>_m</math>\mathrm{MCD}(b_m, ''n'') > 1,</math> allora ''<math>n''</math> non è primo, ed abbiamo finito;
# se M.C.D.(''b''<math>_m</math>\mathrm{MCD}(b_m, ''n'') = 1,</math> calcoliamo ''b''<math>_mb_m^{t}\pmod n</math> (mod ''n''), e procediamo come nel primo test. In questo modo troviamo che ''<math>n''</math> non è primo, oppure che ''<math>n''</math> è pseudoprimo forte in base ''b''<math>_mb_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> _mT_m</math>, sappiamo che la probabilità che n non sia primo e sia uno pseudoprimo forte in base ''b''<math> _mb_m</math> è minore di 1/4, e, quindi, la probabilità che ''<math>n ''</math> non sia primo ma passi i test T<math> _1T_1</math>, T<math> _2T_2</math>, ... , T<math> _mT_m</math> è minore di <math> \left(\frac{1}{4^ {m} }\right)</math>, ossia piccolissima rispetto a quella del [[ Testtest di Fermat]]. ▼
Assumendo l'[[ Ipotesiipotesi 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|pp= 300-317|lingua= inglese }} ([https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf PDF])</ref>. ▼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]].
▲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|pp= 300-317|lingua= inglese }} ([https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf PDF])</ref>.
== Note ==
== Altri progetti ==
{{Interprogetto|preposizione=sul}}
== Collegamenti esterni ==
| 