Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Maria De Falco » 15.Test di Solovay-Strassen e Test di Miller-Rabin


Test di Solovay-Strassen e Test di Miller-Rabin

Un test di primalità è un algoritmo che si applica ad un numero intero con lo scopo di stabilire se esso è primo oppure oppure no.
Si tenga presente che il concetto di test di primalità non va confuso con quello di algoritmo di fattorizzazione, che è invece un algoritmo il cui scopo è quello di determinare i fattori primi di un numero composto.

In questa lezione si esamineranno test di primalità “probabilistici”, cioè, una volta effettuato uno di questi test su un numero positivo n, o si ottiene come risposta che certamente n non è primo, oppure si ottiene una valutazione della probabilità che sia primo.

Test di Solovay-Strassen

Test di primalità di Solovay-Strassen

Sia n un numero naturale dispari≥3.

Si sceglie un numero naturale k≤n e si fissano k basi b1 ,…, bk (cioè k numeri b1 ,…, bk tali che 1≤bi ≤n e (bi ,n)=1).

Per ciascuna base b=bi, si calcolano
b^{\frac{n-1}{2}} modulo n (il che, con il metodo dei quadrati ripetuti, richiede una complessità di O((log n)3) e il simbolo di Jacobi \left(\frac{b_i}{n}\right) (il che, per la Proposizione 13.5, richiede una complessità di O((log n)3).

Se per qualche base bi , b_i^{\frac{n-1}{2}} \not\equiv (\frac{b_i}{n}) \; (mod \; n), allora n non è primo;
se invece per ogni base bi, n supera il test relativamente alla base bi, (cioè b_i^{\frac{n-1}{2}} \equiv (\frac{b_i}{n}) \; (mod \; n)), allora n è “probabilmente primo”.

Test di Miller-Rabin

Sia n un numero naturale dispari≥3, e sia n-1=2st, con t dispari (e quindi s≥1).
Si sceglie un numero naturale k≤n e si fissano  k basi  b1 ,…, bk  (cioè k numeri b1 ,…, bk tali che  1≤bi ≤n e (bi ,n)=1).
Su ciascuna base b=bi , si opera come segue:
(1) si calcola bn-1 modulo n (il che, con il metodo dei quadrati ripetuti, richiede una complessità di O(log n)3);
(2) se bn-1 \not\equiv1 (mod n), allora n non è primo;
se invece bn-1≡1 (mod n), allora si procede con il punto (3);
(3) se b^{\frac{n-1}{2}} \not\equiv \pm 1 \; (mod \; n), allora n non è primo;
se b^{\frac{n-1}{2}}≡-1 (mod n), allora n supera il test relativamente alla base b;
se b^{\frac{n-1}{2}}≡-1 (mod n), allora si procede calcolando b^{\frac{n-1}{4}};
(4) procedendo così, relativamente alla base b, si possono verificare le seguenti possibilità:
(a) bn-1\not\equiv1 (mod n), e in questo caso n non è primo;
(b) esiste 0≤r<s tale che b^{2^{r+1}t}≡1 (mod n), mentre b^{2^rt} \not\equiv \pm1 \;(mod \; n), e in questo caso n non è primo;
(c) bt≡1 (mod n) oppure esiste 0≤r<s tale che b^{2^rt}≡-1 (mod n), e in questo caso n supera il test relativamente alla base b.
Se per ogni base bi , n supera il test relativamente alla base bi , allora n è “probabilmente primo

Validità del test di Solovay-Strassen

Teorema 15.1
Sia n un numero composto dispari. Allora l’insieme
\{ b\in {\mathbf N} \; \vert \; 1\leq b \leq n-1, \; (b,n)=1, \; b^{\frac{n-1}{2}} \equiv (\frac{b}{n}) \; (mod \; n) \}
ha ordine al più \frac{\varphi (n)}{2}.
Dimostrazione
Se esiste un numero primo p tale che p2 divide n,  allora n non è un numero di Carmichael, e l’asserto segue facilmente dal Teorema 14.5.
Si supponga allora che sia n=p1…pt con p1,…,pt primi a due a due distinti.
L’insieme {bє N | 1≤b≤n-1, (b,n)=1, b^{\frac{n-1}{2}}(\frac{b}{n}) (mod n)} è equipotente all’insieme
H={[b]n є Zn* | [b]_n^{\frac{n-1}{2}} = [(\frac{b}{n})]_n}
che, per la Proposizione 14.2 è un sottogruppo di Zn*.

Basta quindi provare che H è un sottogruppo proprio di Zn*.

Validità del test di Solovay-Strassen

Sia a un numero intero tale che \left(\frac{a}{p_1}\right)=-1;

si consideri il sistema di equazioni congruenziali
\left\{\begin{array}{l}x\equiv a (mod\; p_1)\\ \\ x\equiv 1(mod\; p_2...p_t)\end{array}
Tale sistema ammette soluzioni per il Teorema Cinese del Resto; sia b una soluzione di tale sistema
⇒  (\frac{b}{n})=(\frac{b}{p_1}) (\frac{b}{p_2}) \dots (\frac{b}{p_t}) = (\frac{a}{p_1}) (\frac{1}{p_2}) \dots (\frac{1}{p_t})= -1
Inoltre b è coprimo sia con p1 che con p2…pt e quindi b è coprimo con n
⇒ [b]n appartiene a Zn*.
Si supponga per assurdo che [b]n appartenga a H ⇒ b^{\frac{n-1}{2}} \equiv (\frac{b}{n}) \; (mod \; n)⇒ b^{\frac{n-1}{2}} \equiv -1 \; (mod \; n)b^{\frac{n-1}{2}} \equiv -1 \; (mod \; p_2 \dots p_t).

Validità del test di Solovay-Strassen

D’altra parte, b≡1 (mod p2…pt ) ⇒ b^{\frac{n-1}{2}} \equiv 1 \; (mod \; p_2 \dots p_t).
Questa contraddizione prova che [b]n non appartiene a H, sicché H è un sottogruppo proprio di Zn*.

Validità del test di Solovay-Strassen

Sia n un numero naturale dispari≥3, e si supponga che n ha superato il Test di Solovay-Strassen rispetto a k basi; in questo caso, non si ha la certezza che n sia primo, ma dal Teorema 15.1 segue che la probabilità che n sia composto è di \frac{1}{2^k} \; : dunque se il test è stato effettuato  rispetto ad un numero elevato di basi, si è “quasi certi” che n sia primo, ed è quindi ragionevole effettuare su n qualche altro tipo di test, magari più dispendioso, ma che possa dare una risposta certa sulla primalità di n.
Se si vuole, ad esempio abbassare la soglia di errore al di sotto di 10-50, basta effettuare il test su 200 basi.
Se si volesse la certezza assoluta che n è primo, bisognerebbe effettuare il test su un numero di basi maggiore di  \frac{\varphi (n)}{2}

Funzione di Eulero del prodotto di due numeri coprimi

Proposizione 15.2
Sia n=n1n2 con n1 e n2 numeri coprimi e maggiori di 1.
Siano r,c numeri interi, e si ponga X={bє N | 1≤b≤n, (b,n)=1, br≡c (mod n)},
X1={bє N | 1≤b≤n1 , (b,n1)=1, br≡c (mod n1)}, X2={bє N | 1≤b≤n2 , (b,n2)=1, br≡c (mod n2)}
Allora |X|=|X1 x X2|.
Dimostrazione
Si osservi che, se z è un numero intero, allora
1) z è coprimo con n se e solo se z è coprimo sia con n1 che con n2
2) zr≡c (mod n) se e solo se zr≡c (mod n1) e zr≡c (mod n2)

Funzione di Eulero del prodotto di due numeri coprimi

Se b è un qualunque elemento di X, allora b è coprimo sia con n1 che con n2 ; inoltre per ciascun i=1,2, il resto della divisione euclidea di b per ni è congruo a b modulo ni , e quindi appartiene a Xi .
Si consideri la funzione f:X → X1 x X2 definita ponendo f(b)=(r1 , r2), dove ri è il resto delle divisione euclidea di b per ni .
Sia (b1 , b2) un qualunque elemento di X1 x X2 , e si consideri  il sistema di equazioni congruenziali
\left\{\begin{array}{l}x\equiv b_1(mod\; n_1)\\ \\ x\equiv b_2 (mod\; n_2)\end{array}
Per il Teorema Cinese del Resto, esiste una soluzione b di tale sistema tale che 0≤b≤n1n2 .
Per ciascun i=1,2, (bi ,ni)=1 e quindi (b,n1n2)=1  ⇒  b appartiene a X.

Funzione di Eulero del prodotto di due numeri coprimi

D’altra parte, [b]_{n_i}=[b_i]_{n_i} e 1≤bi ≤ni -1 ⇒   bi è il resto delle divisione euclidea di b per ni ⇒ f(b)=(b1 , b2). Dunque f è suriettiva.
Siano ora a,b elementi di X tali che f(a)=f(b)=(r1 , r2)
⇒ a e b sono soluzioni del sistema di equazioni congruenziali
\left\{\begin{array}{l} x \equiv r_1 (mod \; n_1) \\ \\ x\equiv (mod\; n_2)\end{array}
⇒ per il Teorema Cinese del Resto, a=b (perché 1≤a≤n1n2-1 e 1≤b≤n1n2-1). Dunque f è iniettiva.
Dalla biettività di f segue che |X|=|X1 x X2|.

Validità del test di Miller-Rabin

Teorema 15.3
Sia n un numero composto dispari. Allora l’insieme
{bє N | 1≤b≤n-1, (b,n)=1, n è pseudoprimo forte rispetto a b}
ha ordine al più \frac{n-1}{4}.
Non si fornirà la dimostrazione completa del teorema 15.3, ma si darà un’idea di alcuni degli argomenti che vengono utilizzati per dimostrarlo:
Se esiste un numero primo p tale che p2 divide n,  allora n non è un numero di Carmichael, e l’asserto segue facilmente dal Teorema 14.5, dato che
{bє N | 1≤b≤n-1, (b,n)=1, n è pseudoprimo forte rispetto a b} ⊆ {bє N | 1≤b≤n-1, (b,n)=1, bn-1≡1 (mod n)}.
Si supponga allora che sia n=p1…pt con p1,…,pt primi a due a due distinti.
Procederemo nel caso particolare che n sia prodotto di soli due primi distinti p1 e p2 .

Validità del test di Miller-Rabin

Si ponga n-1=2st, p1-1=2hk, p2-1=2uv , con t,k,v dispari (e quindi s,h,u≥1).
Si ha
\left\{ b\in {\mathbf N} \; \vert \; 1\leq b\leq n-1, \; (b,n)=1, \; n \; \grave{e} \; \text{pseudoprimo  forte   rispetto  a  }  b\right\}=X\cup Y^{(0)}\cup Y^{(1)}\cup \dots \cup Y^{(d)}
con
X=\{ b\in {\mathbf N} \; \vert \; 1\leq b\leq n-1, \; (b,n)=1, \; b^t \equiv 1\; (mod\; n) \}
Y^{(r)}= \{ b\in {\mathbf N} \; \vert \; 1\leq b\leq n-1, \; (b,n)=1, \; b^{2^rt} \equiv -1\; (mod\; n) \}
d=min{h,u} – 1

Validità del test di Miller-Rabin

Per la proposizione 15.2, |X|=|X1 x X2| , dove
X_i=\{ b\in {\mathbf N} \; \vert \; 1\leq b\leq p_i -1, \; (b,p_i)=1, \; b^t \equiv 1\; (mod\; p_i) \}
Dato che Z_{p_i}^* è ciclico, |Xi|=(pi-1,t), cioè |X1|=(k,t) e |X2|=(v,t); dunque |X|=(k,t)(v,t)≤kv
Per la proposizione 15.2, \vert Y^{(r)} \vert = \vert Y_1^{(r)} \times Y_2^{(r)}\vert con
Y_i^{(r)}= \{ b\in {\mathbf N} \; \vert \; 1\leq b\leq p_i-1, \; (b,p_i)=1, \; b^{2^rt} \equiv -1\; (mod\; p_i ) \}
Dato che Z_{p_i}^* è ciclico, \vert Y_i^{(r)} \vert =(p_i-1,2^rt), cioè
\vert Y_1^{(r)} \vert =2^r(k,t) e \vert Y_2^{(r)} \vert =2^r(v,t)
Dunque \vert Y^{(r)} \vert =4^r(k,t)(v,t) \leq 4^rkv
Da quanto detto segue che {bє N | 1≤b≤n-1, (b,n)=1, n è pseudoprimo forte rispetto a b} ha ordine al più
kv+kv+4kv+16kv+…+4dkv
Il resto della dimostrazione viene omesso; qui ci si limita a dire che consiste nel “manipolare” il numero kv+kv+4kv+16kv+…+4dkv fino ad ottenere la maggiorazione richiesta.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion