Lezione del giorno 24 aprile 2009
Siamo ora in grado di dimostrare la seconda implicazione del Teorema di Korselt (che caratterizzava i numeri di Carmichael):
Seconda implicazione del Teorema di Korselt:
() Per ipotesi n sia un numero di Carmichael, e dimostriamo che n è prodotto di numeri primi distinti p1,….,pr tali che (pi-1)(n-1) per ogni i=1,….r.
La decomposizione di n in prodotto di potenze di primi distinti sia:
n= p1k1p2k2....prkr.
Dimostriamo che ogni pi ha molteplicità ki=1. Sia per assurdo k1>1 (per esempio), dunque p12n.
Poniamo t= p12 e sia [a] Zt* un generatore del gruppo ciclico Zt* (che esiste per il Teorema precedente): quindi a, t sono coprimi, 1a<tn, [a] ha periodo (t)=p1(p1-1) in Zt*. Consideriamo il numero m=p2....pr; per il Teorema Cinese del Resto, essendo t, m coprimi, esiste un naturale x, con 0x<tmn, soluzione canonica del sistema:
m) (mod 1 x
t) (mod a x
Un tale x è coprimo con n: se per assurdo non lo fosse , x sarebbe multiplo di qualche fattore primo pi di n, quindi o sarebbe multiplo di p1 (ma allora dalla prima congruenza del sistema seguirebbe p1a contro l’ipotesi che a, t sono coprimi) o multiplo di qualche pi con i>1 (ma allora dalla seconda congruenza del sistema seguirebbe pi1, contraddizione perché pi>1).
Dunque x,n sono coprimi e 1x<tmn: essendo n un numero di Carmichael segue:
xn-1 1 (mod n), xn-1 1 (mod t), an-1 1 (mod t), [1]=[a]n-1 Zt*, (n-1) multiplo del periodo p(p-1) di [a], p divisore comune di n,n-1 (contraddizione perché naturali consecutivi sono coprimi).
Dunque è vero che nella decomposizione di n in prodotto di potenze di primi distinti, ogni fattore pi
ha molteplicità ki=1, cioé n è prodotto di primi distinti: p1p2....pr. Resta da dimostrare che (n-1) è multiplo di (pi-1) per ogni i.
Fissato per esempio p=p1 , sia [b]Zp* un generatore del gruppo ciclico Zp*; quindi b, p sono coprimi, 1b<pn, [b] ha periodo (p)=p-1 in Zp*.
Consideriamo il numero m=p2....pr; per il Teorema Cinese del Resto, essendo p, m coprimi, esiste un naturale x, con 0x<pm=n, soluzione canonica del sistema:
m) (mod 1 x
p) (mod b x
Come sopra si deduce che x,n sono coprimi, 1x<pm=n, [1]=[b]n-1Zp*, (n-1) multiplo del periodo (p-1) di [b]. Con ragionamento analogo si ha che (n-1) è multiplo di (pi-1) per ogni i.
Test di primalità di Rabin-Miller
E’ un test di primalità probabilistico, che si applica ad un input n>1 naturale dispari (non è una restrizione sostanziale perché un naturale pari è sempre composto, tranne nel caso n=2).
Rispetto al test di Fermat non presenta “eccezioni” (come i numeri di Carmichael) ed inoltre la probabilità che un numero composto superi il test è 1/4 (contro il 1/2 del test di Fermat per i numeri non di Carmichael).
I passi dell’algoritmo del test di Rabin-Miller sono:
1) in input il naturale n>1 dispari
2) si calcola la massima potenza 2s di base 2 ed esponente s>0 tale che 2s sia divisore del numero pari n-1, e dunque si rappresenta (n-1) nella forma: n-1=2st, con t>0 naturale dispari
3) si sceglie casualmente un intero a con 1an-1 (detto base)
4) si costruiscono le riduzioni modulo n delle s potenze di base a ed esponente t, 21t, 22t, ….. , 2s-1t:
a2itmodn i=0,1,…..,s-1 5) se è verificata almeno una delle seguenti condizioni:
at modn =1 oppure a2itmodn =n-1 per qualche i=0,1,….,s-1
si esce con output ”n è primo”, altrimenti si esce con output “n è composto”.
Notiamo che le condizioni del passo 5) equivalgono alle congruenze:
at1 (mod n), a2it-1 (mod n).
Verifichiamo prima di tutto che un input n primo (dispari) supera sempre il test.
Utilizzeremo la proprietà seguente: se n è primo e se x è un naturale tale che x21 (mod n) , allora x1 (mod n) (infatti da x21 (mod n) segue n(x2-1), n(x-1)(x+1), n(x-1) oppure n(x+1)).
Supponiamo dunque l’input n primo (dispari) e per assurdo supponiamo non verificata nessuna delle condizioni del passo 5); essendo a non multiplo di n (perché a<n), per il Piccolo Teorema di Fermat si ha:
an-1=a2st=(a2s-1t)21 (mod n)
e per quanto detto sopra si ha a2s-1t1 (mod n), ma allora (non essendo per assurdo verificata nessuna delle condizioni del passo 5)) a2s-1t=(a2s-2t)21, a2s-2t1, a2s-2t1, e così via procedendo a ritroso, fino ad arrivare ad a21t=(at)21, at1, contraddizione perchè at1, at
-1 sono fra le condizioni del passo 5).
Esaminiamo poi la complessità dell’algoritmo.
Sia k=L(n) la lunghezza binaria dell’input n.
Nel passo 2), per rappresentare n-1 nella forma n-1=2st, con t>0 naturale dispari, si tratta di effettuare s successive divisioni per 2 (fermandosi quando il quoziente è dispari): queste divisioni consistono semplicemente nell’elidere le cifre =0 a destra nella rappresentazione binaria di n-1.
Inoltre il numero s di tali divisioni è <k=L(n): infatti 2s2st=n-1<n<2k.
Nel passo 4) si tratta di calcolare (come già notato) le riduzioni modulo n delle s potenze:
a2itmodn dove i=0,1,….,s-1
ognuna con esponente <n e con base <n, e si può utilizzare l’esponenziazione modulare, che ha complessità polinomiale di ordine O(k3) (notare anche che si possono semplificare i calcoli osservando che ognuna di tali s potenze è il quadrato della precedente, quindi dal calcolo della riduzione modulo n della prima at si possono ricavare facilmente le riduzioni delle successive, quadrando ripetutamente). Poiché (come già notato) è s<k, l’algoritmo ha in totale complessità polinomiale di ordine O(k4).
