Test di primalità

Esistono dei test probabilistici per testare se $n$$n$ è primo.

Definizione (394 Pseudo-primo)

$n$$n$ si dice uno pseudo-primo rispetto alla base $b$$b$ se $b^{n-1}\equiv 1\mod n$$b^{n-1}\equiv 1\mod n$, dove $0<b<n$$0<b<n$, e se $M.C.D.(b,n)=1$$M.C.D.(b,n)=1$.

 

Passi del test di primalità:

1. Scegli $b$$b$ con $0<b<n$$0<b<n$ e calcola $d=M.C.D.(b,n)$$d=M.C.D.(b,n)$.
2. Se $d$$d$ è diverso da 1, $n$$n$ non è primo (costo di $\log n$$\log n$ operazioni).
3. Se $d=1$$d=1$, calcolo $b^{n-1}\mod n$$b^{n-1}\mod n$.
4. Se $[b^{n-1}]_{n}\neq [1]_{n}$$[b^{n-1}]_{n}\neq [1]_{n}$, restituisce "$n$$n$ non primo".
5. Se $[b^{n-1}]_{n}=[1]_{n}$$[b^{n-1}]_{n}=[1]_{n}$, restituisci "$n$$n$ è pseudoprimo rispetto alla base $b$$b$".

Questo test funziona perché, se $n$$n$ fosse primo, si avrebbe $\phi (n)=n-1$$\phi (n)=n-1$. Per Eulero-Fermat, con $b,n$$b,n$ coprimi, si avrebbe $b^{\phi (n)}\equiv 1\mod n$$b^{\phi (n)}\equiv 1\mod n$, quindi $b^{n-1}\equiv 1\mod n$$b^{n-1}\equiv 1\mod n$. Quindi se questo non avviene il numero non è primo. Tuttavia se si ha $b^{n-1}\equiv 1\mod n$$b^{n-1}\equiv 1\mod n$, non è detto che il numero sia primo.

Ci sono numeri che risultano pseudoprimi per qualsiasi base $b$$b$ anche se non sono numeri primi.

Definizione (395 Primo di Carmichael)

Un numero $n$$n$ si dice primo di Carmichael se $n$$n$ è pseudoprimo rispetto a ogni $b$$b$ con $0<b<n$$0<b<n$.

 

Lemma sugli pseudoprimi

Lemma (396)

Sia $n$$n$ un numero naturale, allora

1. se $n$$n$ è pseudoprimo rispetto alle basi $b_{1},b_{2}$$b_{1},b_{2}$, allora è pseudoprimo rispetto alla base $b_{2}b_{1}^{-1}$$b_{2}b_{1}^{-1}$
2. se esiste una base $b$$b$ per cui $n$$n$ non è uno pseudoprimo, allora ce ne sono almeno $\phi (n)/2$$\phi (n)/2$ con tale proprietà.

 

Dimostrazione

Dimostro il punto 2 del lemma: Siano $b_{1},\dots ,b_{t}$$b_{1},\dots ,b_{t}$ tutte le basi per cui $n$$n$ è pseudoprimo, e sia $c$$c$ una base per cui $n$$n$ non è pseudoprimo. Allora

$$b_{i}^{n-1}\equiv 1\mod n.$$

$$b_{i}^{n-1}\equiv 1\mod n.$$

Considero i numeri $cb_{1},cb_{2},\dots ,cb_{t}$$cb_{1},cb_{2},\dots ,cb_{t}$, allora $n$$n$ non è pseudoprimo per nessuno di queste basi, che sono almeno $t$$t$. Questo mostra che il numero di basi per cui $n$$n$ non è pseudoprimo è almeno quanto il numero di basi per cui $n$$n$ è pseudoprimo. Sia $s$$s$ il numero di basi per cui $n$$n$ non è pseudoprimo. Allora $s\geq t$$s\geq t$, inoltre $s+t=\phi (n)$$s+t=\phi (n)$, perché $s+t$$s+t$ è il numero totale di elementi coprimi con $n$$n$. Unendo le due equazioni $s+t=\phi (n)$$s+t=\phi (n)$ e $s+t\leq 2s$$s+t\leq 2s$, si ha $\phi (n)\leq 2s$$\phi (n)\leq 2s$, cioè $s\geq \phi (n)/2$$s\geq \phi (n)/2$.

 

Lemma (397)

1. Se $n$$n$ è primo di Carmichael, allora $n$$n$ è senza quadrati (come i numeri utilizzati nel protocollo RSA).
2. $n$$n$ è primo di Carmichael se e solo se $p-1\mid n-1$$p-1\mid n-1$ per ogni divisore primo di $n$$n$;
3. se $n$$n$ è primo di Carmichael, allora $n$$n$ è divisibile per almeno tre primi.

 

Esempio (398 applicazione del lemma)

$561=3*11*17$$561=3*11*17$. $n-1=560$$n-1=560$. I divisori primi di $n$$n$ sono $p_{1}=3,p_{2}=11,p_{3}=17$$p_{1}=3,p_{2}=11,p_{3}=17$, e si ha che $2,16,10$$2,16,10$ dividono $560$$560$, cioè per ogni divisore $p-1\mid n$$p-1\mid n$, e quindi $561$$561$ è il più piccolo primo di Carmichael. Senza conoscere la fattorizzazione di $561$$561$, basta estrarne la radice cubica e verificare se ha divisori.