Teoria dei numeri e Crittografia: lezione del 4 maggio 2011Osserviamo che il test di primalità di Fermat ha complessità O(x3)

Teoria dei numeri e Crittografia: lezione del 4 maggio 2011

Osserviamo che il test di primalità di Fermat ha complessità  O(x

) se x=L(n): infatti tratta di calcolare il mcd(a,n) con l’algoritmo Euclideo e la riduzione a

modn con l’algoritmo dell’esponenziazione modulare (entrambi di complessità  O(x

)).

Un numero composto n supera (erroneamente) il test quando nello stesso tempo:

- d=mcd(a,n)=1 (ossia se la base casuale a è un numero coprimo con n) - si ha y=a

modn=1.

Un input composto n che superi il test di Fermat relativamente alla scelta della base a è detto pseudoprimo nella base a (perché n “finge” di essere primo, superando il test per quella particolare scelta di a): per quanto osservato sopra ciò equivale ad affermare che contemporaneamente:

mcd(a,n)=1, a

modn=1 (sempre con 1 a  n-1)

In effetti però affinché un n>1 composto sia pseudoprimo nella base a (con 1 a  n-1) basta che sia a

modn=1: infatti se ciò è vero allora certamente mcd(a,n)=1 (se per assurdo d= mcd(a,n)>1, scelto un divisore primo p di d si avrebbe p a

, p n da cui la contraddizione p 1, tenendo conto che a

 1 (mod n)).

Esempio.

Si consideri il numero composto n=341=1131.

Si ha 2

mod341=1 (come già calcolato nell’esempio di applicazione dell’esponenziazione modulare). Dunque n=341 é pseudoprimo nella base a=2, e supera (erroneamente) il test di Fermat per tale scelta di a.

Ma con l’esponenziazione modulare si ottiene anche (dopo avere fatto i dovuti calcoli):

3

mod341=561,

Dunque n=341 non è pseudoprimo nella base a=3, e in tale base non supera il test, rivelando di essere in effetti composto .

Calcoliamo ora un maggiorante per la probabilità che un numero composto n superi il test di Fermat.

Il numero dei valori possibili per la scelta dell’elemento casuale a nel test è (n-1); vediamo come possiamo valutare il numero dei valori a per i quali il test è superato, cioè il numero delle possibili basi in cui l’input n è pseudoprimo:

Teorema.

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

modn1 (notiamo che in tale base n non è pseudoprimo).

Allora il numero delle basi a in cui n è pseudoprimo è  (n)/2.

Di questo Teorema daremo in seguito la dimostrazione: prima osserviamo alcune sue conseguenze.

Se n è un naturale composto, e se soddisfa le ipotesi del Teorema precedente, la probabilità che n superi il test di Fermat (per una scelta casuale della base a) è  1/2. Infatti il numero delle basi a (comprese fra 1 ed n-1) in cui n è pseudoprimo (cioè supera il test) è  (n)/2 (n-1)/2, e la probabilità che a sia scelto casualmente fra questi valori è allora  [(n-1)/2]/(n-1)=1/2.

Ripetendo k volte il test, ogni volta con una scelta casuale indipendente del valore della base a, la probabilità che un numero composto (che verifica le ipotesi del Teorema) superi tutte le k volte il test di Fermat è 1/2

, quindi tale probabilità può essere resa piccola a piacere (per k sufficientemente grande).

Per esempio se k=100 tale probabilità è 1/2

1/10

.

Dunque se l’input n supera k volte il test di Fermat, con k abbastanza grande, possiamo affermare che n è primo, con una probabilità di errore molto bassa, eccetto che nel caso in cui n sia un numero composto che non soddisfa le ipotesi del Teorema precedente.

Problema: cosa avviene di tale probabilità di errore nel caso in cui il numero naturale n composto dato in input non soddisfa le ipotesi del Teorema precedente ? Esistono tali numeri n ?

Per un naturale n composto che non soddisfa le ipotesi del Teorema precedente si ha che per ogni intero a tale che 1 a  n-1, e tale che mcd(a,n)=1, si ha sempre a

modn=1 (quindi in tutte queste basi n è pseudoprimo). Dunque il numero delle basi a in cui n è pseudoprimo é =(n).

Si deduce che, per un tale n, la probabilità che n superi il test è =(n)/(n-1) , e se usiamo la formula per calcolare (n) conoscendo la fattorizzazione di n in potenze di fattori primi distinti p

,p

,…,p

: (n) = n(1-1/p

)(1-1/p

)...(1-1/p

)

otteniamo che tale probabilità è :

(n)/(n-1)  (n)/n =(1-1/p

)(1-1/p

)...(1-1/p

)

Se i fattori primi p

sono molto “grandi”, tale probabilità è molto vicina ad 1, quindi molto alta:

sottoponendo un tale input n al test di Fermat anche un numero molto grande di volte, è molto probabile che superi sempre il test.

Definizione. Un numero naturale composto n che soddisfa la condizione:

per ogni intero a tale che 1 a n-1, e tale che mcd(a,n)=1, si ha sempre a

modn=1 è detto numero di Carmichael.

Esempio: Un numero di Carmichael molto grande è n=225.593.397.919 (si dimostra che è di Carmichael con il Teorema di Korselt che vedremo in seguito): la sua decomposizione in fattori primi è 2207661915443 . Per tale input n la probabilità che n superi il test di Fermat è circa:

(1-1/2207)(1-1/6619)(1-1/15443)  0,99933 (molto vicina al 100%).

Diamo ora la dimostrazione del Teorema enunciato sopra:

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

modn=1} l’insieme delle basi in cui n è pseudoprimo, e sia b come nell’enunciato. Ricordiamo, come osservato prima, che se aS si ha certamente mcd(a,n)=1 , quindi [a],[b]Z

*, ed anche [a][b]=[ab]Z

*.

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 e compresi fra 1 ed (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, si ha [t]= [ab]Z

* (come osservato sopra).

Inoltre gli elementi di T sono nell’intervallo [1,n-1] (perché riduzioni modulo n di numeri coprimi con n quindi non multipli di n).

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

a

b

b

(mod n) quindi t

modn=b

modn1, ossia tS.

Dunque S,T sono insiemi disgiunti della stessa cardinalità, entrambi contenuti nell’insieme dei

numeri naturali dell’intervallo [1,n-1] coprimi con n: si conclude che 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 per ogni fattore primo p di n si ha (p-1)(n-1) .

Dimostrazione.

() Per ipotesi n=p

p

….p

, con p

primi distinti tali che (p

-1)(n-1) per ogni i . La tesi è che per ogni a intero tale che 1 a n-1, mcd(a,n)=1, si ha a

modn=1 ossia:

a

1 (mod n).

Essendo a,n coprimi, nessun p

è divisore di a, quindi, per il Piccolo Teorema di Fermat:

i 1

a

1 (mod p

)

Se n-1=k(p

-1) si ha a

=

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.

() (omettiamo questa parte della dimostrazione, che si basa sulla 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 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 “efficiente” (valido però solo per un input 3,410

) eliminando la scelta casuale della base a, e ripetendo invece il test esattamente 7 volte, una per ognuna delle basi elencate (la complessità resta ovviamente  O(x

) se x=L(n)).

Radici primitive modulo n

Torniamo al caso di un gruppo commutativo finito G di cardinalità n, e di un elemento aG di periodo k=ord(a) (dunque k è il minimo esponente intero positivo tale che a

=1

). Sappiamo allora che l’insieme delle potenze di base a ad esponente intero  0 è formato dalle k potenze distinte con esponente i=0,1,2,….,k-1:

a

=1

, a

=a

a

,……, a

Inoltre per ogni esponente intero h0 si ha: a

=1

 k=ord(a) è divisore di h.

Infine per ogni coppia di esponenti interi h,s0 si ha: a

=a

 hs (mod k).

Ricordiamo anche che il periodo k=ord(a) è sempre divisore della cardinalità n di G.

Se le potenze distinte di base a esauriscono tutti gli elementi del gruppo G, si dice che G è gruppo ciclico generato da a e l’elemento a è detto generatore di G: in questo caso ogni elemento di G sarà una potenza di base a ad esponente intero  0 e  k-1 (dove k=ord(a)), e la cardinalità di G coinciderà con il periodo k del generatore a.

Per verificare se un gruppo G commutativo finito di cardinalità n è ciclico basta dunque verificare l’esistenza di almeno un elemento aG di periodo uguale ad n: infatti, se un tale a esiste, l’insieme delle potenze distinte di base a ha cardinalità n, dunque necessariamente coincide con G.

Esempio:

Nel gruppo moltiplicativo Z

*= {[1], [2], [3], [4]} degli elementi invertibili di Z

, cioè delle classi di congruenza modulo 5 con rappresentante coprimo con 5, il periodo dell’elemento a=[2] è 4 (in quanto [2]

=[4], [2]

=[8]=[3], [2]

=[16]=[1]=elemento neutro), dunque coincide con la cardinalità di Z

*. Si conclude che Z

* è gruppo ciclico con generatore [2].

Nel gruppo moltiplicativo Z

*= {[1], [3], [5], [7]} degli elementi invertibili di Z

, cioè delle classi di congruenza modulo 8 con rappresentante coprimo con 8, si verifica che nessun elemento ha periodo uguale alla cardinalità 4 di Z

* (il quadrato di ogni elemento al quadrato coincide con l’elemento neutro), dunque Z

* non è gruppo ciclico.

Vedremo in seguito (Teorema di Gauss) per quali valori di n il gruppo moltiplicativo Z

* è ciclico.

Se il gruppo moltiplicativo Z

* (degli elementi invertibili di Z

) è ciclico per un certo valore di n, chiameremo radice primitiva modulo n ogni intero a tale che 1 a n-1, a,n sono coprimi e tale che [a]Z

* sia un generatore del gruppo ciclico Z

* (quindi le radici primitive modulo n sono in numero uguale a quello dei generatori di Z

*). Per esempio, come visto sopra, 2 è una radice primitiva modulo 5, ma non esistono radici primitive modulo 8.

Se a è una radice primitiva modulo n, in Z

* l’elemento [a] ha periodo uguale a (n) (funzione di Eulero di n) perché (n) è la cardinalità di Z

*, e le potenze di [a] con esponenti 0,1,….., (n)-1 esauriscono tutti gli elementi di Z

*: dunque le riduzioni modulo n delle potenze di a con esponenti 0,1,….., (n)-1 esauriscono tutti i numeri naturali x<n che sono coprimi con n.

Gauss trovò tutti e soli i valori n>1 per i quali il gruppo moltiplicativo Z

* è ciclico (e per i quali dunque esiste qualche radice primitiva modulo n):

Teorema di Gauss.

Dato un naturale n>1:

il gruppo moltiplicativo Z

* è ciclico  n é uno dei seguenti valori: 2, 4, p

(con p primo >2 , k>0), 2p

(con p primo >2 , k>0).

(poiché la dimostrazione generale di tale risultato è molto complessa, dimostreremo in seguito solo i

casi di p e p

, con p primo).