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 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
modulo n (il che, con il metodo dei quadrati ripetuti, richiede una complessità di O((log n)3) e il simbolo di Jacobi (il che, per la Proposizione 13.5, richiede una complessità di O((log n)3).
Se per qualche base bi , , allora n non è primo;
se invece per ogni base bi, n supera il test relativamente alla base bi, (cioè ), allora n è “probabilmente primo”.
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 1 (mod n), allora n non è primo;
se invece bn-1≡1 (mod n), allora si procede con il punto (3);
(3) se , allora n non è primo;
se ≡-1 (mod n), allora n supera il test relativamente alla base b;
se ≡-1 (mod n), allora si procede calcolando ;
(4) procedendo così, relativamente alla base b, si possono verificare le seguenti possibilità:
(a) bn-11 (mod n), e in questo caso n non è primo;
(b) esiste 0≤r<s tale che ≡1 (mod n), mentre , e in questo caso n non è primo;
(c) bt≡1 (mod n) oppure esiste 0≤r<s tale che ≡-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
Teorema 15.1
Sia n un numero composto dispari. Allora l’insieme
ha ordine al più .
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, ≡ (mod n)} è equipotente all’insieme
H={[b]n є Zn* | }
che, per la Proposizione 14.2 è un sottogruppo di Zn*.
Basta quindi provare che H è un sottogruppo proprio di Zn*.
Sia a un numero intero tale che ;
si consideri il sistema di equazioni congruenziali
Tale sistema ammette soluzioni per il Teorema Cinese del Resto; sia b una soluzione di tale sistema
⇒
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 ⇒ ⇒ ⇒.
D’altra parte, b≡1 (mod p2…pt ) ⇒ .
Questa contraddizione prova che [b]n non appartiene a H, sicché H è un sottogruppo proprio di Zn*.
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 : 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
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)
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
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.
D’altra parte, 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
⇒ 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|.
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ù .
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 .
Si ponga n-1=2st, p1-1=2hk, p2-1=2uv , con t,k,v dispari (e quindi s,h,u≥1).
Si ha
con
d=min{h,u} – 1
Per la proposizione 15.2, |X|=|X1 x X2| , dove
Dato che è 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, con
Dato che è ciclico, , cioè
e
Dunque
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.
1. Espansione di un numero naturale in base b e complessità computazionale delle operazioni elementari
2. Complessità dell'algoritmo delle divisioni successive
3. Struttura dell'anello degli interi modulo m, funzione di Eulero
4. Equazioni congruenziali lineari e Teorema Cinese del Resto
5. Teorema di Fermat-Eulero e Piccolo teorema di Fermat. Alcune proprietà dei gruppi ciclici finiti
6. Cifrario di Cesare. Cifrario di Vigenere. Metodo di Hill
7. Richiami sui campi finiti. Generalità sulle curve ellittiche
10. RSA. Sistema di di Massey-Omura. Sistema di El Gamal
11. Immersione dei testi in chiaro e sistemi crittografici in una curva ellittica
12. Resti quadratici e simbolo di Legendre
13. Condizioni necessarie e condizioni sufficienti per la primalità; forme di pseudoprimalità
15. Test di Solovay-Strassen e Test di Miller-Rabin
16. Test di primalità basato sulle curve ellittiche e test AKS