Pseudoprimo forte

Sia $b$ un intero, e sia $n$ un intero dispari positivo, non primo, e tali che $b<n$ , e $\mathrm {MCD} (b,n)=1$ . Scriviamo $n=2^{s}\cdot t+1$ , con $t$ dispari. Il numero $n$ si dice uno pseudoprimo forte in base $b$ se vale una delle seguenti condizioni:

$b^{t}\equiv 1{\pmod {n}}$
esiste un $r$ in $\mathbb {N}$ , con $r<s$ , tale che $b^{2^{r}\cdot t}\equiv -1{\pmod {n}}$ .

In altre parole, $n$ è uno pseudoprimo forte se è uno pseudoprimo per il test di Miller-Rabin.

Proprietà[modifica | modifica wikitesto]

Sia $n$ un numero intero positivo dispari e $b<n$ un intero positivo tale che $\mathrm {MCD} (b,n)=1$ . Se $n\equiv 3{\pmod {4}}$ , allora $n$ è uno pseudoprimo forte in base $b$ se e solo se $n$ è uno pseudoprimo di Eulero-Jacobi in base $b$ .

Infatti, se $n\equiv 3{\pmod {4}}$ , segue facilmente che $s=1$ . Quindi, $n$ è uno pseudoprimo forte in base $b$ se e solo se:

b^{(n-1)/2}\equiv 1{\pmod {n}}

, oppure

b^{(n-1)/2}\equiv -1{\pmod {n}}

.

Se $n$ è uno pseudoprimo di Eulero-Jacobi-Jacobi in base $b$ , si ha:

b^{(n-1)/2}\equiv \left({\frac {b}{n}}\right){\pmod {n}},

dove a destra abbiamo il simbolo di Jacobi. Quindi

b^{(n-1)/2}\equiv 1{\pmod {n}}

, oppure

b^{(n-1)/2}\equiv -1{\pmod {n}}

,

ed $n$ è uno pseudoprimo forte in base $b$ .

Viceversa, sia $n$ uno pseudoprimo forte in base $b$ . Poiché $n\equiv 3{\pmod {4}}$ , si ha che: $\left({\frac {\pm 1}{n}}\right)=\pm 1,$ e, dunque,

\left({\frac {b}{n}}\right)=\left({\frac {b\cdot b^{2(n-3)/4}}{n}}\right)=\left({\frac {b^{(n-1)/2}}{n}}\right)=\left({\frac {\pm 1}{n}}\right)=\pm 1\equiv b^{(n-1)/2}{\pmod {n}}.

Vi sono altre due proprietà, che elenchiamo senza dimostrazione.

Sia $n$ un numero intero positivo dispari e $b<n$ un numero intero positivo tale che $\mathrm {MCD} (b,n)=1$ . Se $n$ è uno pseudoprimo forte in base $b$ , allora $n$ è uno pseudoprimo di Eulero-Jacobi in base $b$ .
Sia $n$ un numero intero positivo dispari e non primo. I numeri positivi $b<n$ tali che $\mathrm {MCD} (b,n)=1$ , e tali che $n$ sia uno pseudoprimo forte in base $b$ sono non più di un quarto di tutti i numeri positivi $b<n$ tali che $\mathrm {MCD} (b,n)=1$ .

Gli pseudoprimi forti hanno un importante ruolo nella crittografia moderna, poiché sono spesso utilizzati in algoritmi che sfruttano test di primalità probabilistici, come RSA, che usa l'algoritmo del test di Miller - Rabin per trovare dei numeri primi molto grandi.