Pseudoprimo forte

Template:F Sia $b$ un intero, e sia $n$ un intero dispari positivo, non primo, e tali che $b<n$, e $\mathrm{M}\mathrm{C}\mathrm{D}(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:

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

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

Proprietà

Sia $n$ un numero intero positivo dispari e $b<n$ un intero positivo tale che $\mathrm{M}\mathrm{C}\mathrm{D}(b,n)=1$. Se $n\equiv 3(\mathrm{mod}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(\mathrm{mod}4)$, segue facilmente che $s=1$. Quindi, $n$ è uno pseudoprimo forte in base $b$ se e solo se:

$b^{(n-1)/2}\equiv 1(\mathrm{mod}n)$, oppure $b^{(n-1)/2}\equiv -1(\mathrm{mod}n)$.

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

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

dove a destra abbiamo il simbolo di Jacobi. Quindi

$b^{(n-1)/2}\equiv 1(\mathrm{mod}n)$, oppure $b^{(n-1)/2}\equiv -1(\mathrm{mod}n)$,

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

Viceversa, sia $n$ uno pseudoprimo forte in base $b$. Poiché $n\equiv 3(\mathrm{mod}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}(\mathrm{mod}n).$

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

1. Sia $n$ un numero intero positivo dispari e $b<n$ un numero intero positivo tale che $\mathrm{M}\mathrm{C}\mathrm{D}(b,n)=1$. Se $n$ è uno pseudoprimo forte in base $b$, allora $n$ è uno pseudoprimo di Eulero-Jacobi in base $b$.
2. Sia $n$ un numero intero positivo dispari e non primo. I numeri positivi $b<n$ tali che $\mathrm{M}\mathrm{C}\mathrm{D}(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{M}\mathrm{C}\mathrm{D}(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.

Voci correlate

• Piccolo teorema di Fermat
• Numero primo
• Pseudoprimo
• Pseudoprimo di Eulero
• Test di Wilson
• Test di Lucas-Lehmer
• Test di Miller-Rabin

Collegamenti esterni

• Template:Collegamenti esterni