Sia n un numero naturale, e supponiamo che esista almeno un naturale b, con 1bn-1, mcd(b,n)=1, tale che b

Lezione del giorno 16 aprile 2009

Forniamo ora la dimostrazione del Teorema enunciato nella lezione precedente:

Teorema.

Sia n un numero naturale, e supponiamo che esista almeno un naturale b, con 1bn-1, mcd(b,n)=1, tale che b

modn1. Allora il numero dei naturali a tali che 1an-1, mcd(a,n)=1, a

modn=1 (cioè il numero delle basi in cui n è pseudoprimo) è (n)/2.

Dimostrazione: Sia S = {aN / 1an-1, mcd(a,n)=1, a

modn=1}, e sia b come nell’enunciato. Al variare di aS, consideriamo l’insieme T delle riduzioni modulo n dei prodotti ab:

T = { (ab)modn / aS }

Tali elementi in T, al variare di aS, sono distinti: infatti se per assurdo (ab)modn=(cb)modn con a,cS distinti, si avrebbe nel gruppo moltiplicativo Z

* [a][b]=[c][b], e per la legge di cancellazione [a]=[c], contraddizione perché a,c sono distinti nell’intervallo [1,n-1], quindi le classi di congruenza [a],[c] sono distinte. Dunque S,T hanno stessa cardinalità.

Gli elementi di T sono coprimi con n : se t=(ab)modnT, allora in Z

si ha [t]=[a][b] Z

* perché [a],[b] Z

*, dunque mcd(t,n)=1. Inoltre gli elementi di T sono nell’intervallo [1,n-1] (perché riduzioni modulo n).

Per ogni t=(ab)modnT, si ha t

a

b

b

quindi t

modn=b

modn1, ossia tS. Dunque S,T sono insiemi disgiunti della stessa cardinalità, entrambi contenuti nell’insieme dei naturali dell’intervallo [1,n-1] coprimi con n: dunque la cardinalità di S è  della metà del numero di questi naturali cioè è (n)/2, come si voleva dimostrare.

Il matematico Korselt ha caratterizzato i numeri di Carmichael:

Teorema di Korselt.

Un numero naturale composto n è un numero di Carmichael  n è prodotto di primi distinti, e ogni fattore primo p

soddisfa la condizione (p

-1)(n-1) .

Dimostrazione.

() Per ipotesi n=p

p

….p

, con p

primi distinti tali che (p

-1)(n-1).

Sia a intero tale che 1an-1, mcd(a,n)=1, e dimostriamo che a

modn=1 ossia che a

1 (mod n).

Essendo a,n coprimi, nessun p

è divisore di a, quindi, per il Piccolo Teorema di Fermat, _a ^p

^{ 1} 1 (mod p

), e se n-1=k(p

-1) si ha a

= a ^k(p

^{ 1)} 1

=1 (mod p

), per ogni i=1,….,r .

Ogni p

è divisore di a

-1, e poiché i p

(primi distinti) sono a 2 a 2 coprimi, il loro prodotto n è divisore di a

-1 e si ha la tesi.

() Dimostreremo questa implicazione dopo lo sviluppo della teoria delle radici primitive modulo n.

Possiamo notare che un numero di Carmichael n è prodotto di almeno 3 fattori primi distinti: se per assurdo fosse n=pq, con p,q primi distinti, per esempio con p<q, per il Teorema di Konselt si avrebbe (q-1)(n-1), da cui n-1=pq-1=(q-1)t, con t naturale, (p-1)=(q-1)(t-p), p-1q-1, pq, contraddizione.

Il più piccolo numero di Carmichael è n=561 la cui decomposizione in fattori primi è 3 1117 (e infatti 2, 20, 16 sono divisori di n-1=560).

Un esempio di numero di Carmichael molto grande (già citato) è n=225.593.397.919 la cui

decomposizione in fattori primi è 2207661915443 (si verifica facilmente che 2207, 6619, 15443

sono primi e che 2207-1, 6619-1, 15443-1 sono divisori di n-1).

Empiricamente si è verificato che i numeri di Carmichael sono abbastanza “rari”: quelli < 2510

sono “soltanto” in numero di 2.163: questo è un fatto positivo, perché la probabilità che l’input n del test di Fermat sia un numero di Carmichael è relativamente bassa.

D’altra parte è stato dimostrato (1992) che i numeri di Carmichael sono infiniti, e questo è un fatto negativo, perché per quanto grande sia l’input n del test di Fermat, esiste sempre la possibilità che sia un numero di Carmichael.

La possibilità di imbattersi in un numero di Carmichael rende il test di Fermat non molto affidabile, ma si è osservato che nessun naturale composto x3,410

è pseudoprimo contemporaneamente in tutte le seguenti basi: 2,3,5,7,11,13,17 (i primi 7 numeri primi); dunque si può trasformare il test di Fermat in un test di primalità deterministico (valido solo per un input 3,410

) eliminando la scelta casuale della base a, e ripetendo il test esattamente 7 volte, una per ognuna delle basi elencate.

Osservazioni sulla probabilità nei test di primalità

Un test di primalità probabilistico fornisce a priori una maggiorazione per la probabilità che un input composto n superi il test per k volte (con k fissato): per esempio nel test di Fermat la probabilità è 1/2

(tranne nel caso di un numero di Carmichael). In generale in un test probabilistico la probabilità che un input composto n superi il test per k volte (con k fissato) è 1/C

con C costante opportuna.

La vera questione è però quella inversa: se l’input n ha superato k volte il test, cosa possiamo dire della probabilità che sia composto ?

Nel linguaggio del calcolo della probabilità: dati 2 eventi A, B, indichiamo con p(A/B) la probabilità “condizionale” che si verifichi l’evento A, sotto la condizione che si sia verificato l’evento B; se A=”l’input è composto”, B=”l’input ha superato k volte il test”, ed è nota una maggiorazione per p(B/A), cosa possiamo dire su p(A/B) ?

Vedremo che è possibile dare una risposta utilizzando il Teorema di Bayes:

p(A/B) = p(B/A)p(A)/p(B) (dove p(A), p(B) sono le probabilità assolute degli eventi A,B)