I Teoremi di Euclide ed Eulero dimostrati nell’ultima lezione hanno come conseguenza che, dato un numero naturale pari n, esso è perfetto se e solo se n=2

Teoria dei numeri e Crittografia: lezione del 16 maggio 2011

I Teoremi di Euclide ed Eulero dimostrati nell’ultima lezione hanno come conseguenza che, dato un numero naturale pari n, esso è perfetto se e solo se n=2

(2

-1)=2

M

dove M

è un numero di Mersenne primo.

Dunque esiste una biiezione fra numeri perfetti pari e numeri di Mersenne primi: poiché si conoscono a tutt’oggi 46 numeri di Mersenne primi, si conoscono altrettanti numeri perfetti pari.

E’ ancora aperta la congettura: esiste un numero perfetto dispari ? Il test di primalità AKS (cenni).

E’ l’unico test di primalità deterministico di complessità polinomiale che si conosca a tutt’oggi.

E’ stato implementato nel 2002 da tre matematici indiani: Agrawal, Kayal, Saxena.

Osserviamo prima di tutto che:

se n è un numero primo, i coefficienti binomiali _



 



 i

n con 1 i n-1 sono tutti multipli di n.

Infatti si ha _



 



 i

n = _i!(n ^n! _{ 1 )!} dunque i!(n-1)! _



 



 i

n = n!, ossia il numero primo n è divisore del

prodotto i!(n-1)! _



 



 i

n , e poiché n non è divisore né di i! né di (n-1)! (che sono prodotti di fattori <n,

dunque non multipli di n), si ha che n è divisore di _



 



 i n .

Su tale osservazione si basa un test di primalità deterministico che ora esporremo.

Fissiamo un polinomio h(x)Z[x] . Dati due polinomi f(x), g(x)Z[x] diremo che f(x) è congruo g(x) modulo h(x) se h(x)f(x)-g(x) cioè se esiste s(x)Z[x] tale che f(x)-g(x)=s(x)h(x). In tale caso scriveremo f(x) g(x) (mod h(x)).

E’ facile verificare che tale relazione di congruenza fra polinomi è una relazione di equivalenza in Z[x], e che gode di proprietà simili a quelle della congruenza fra interi: essa è per esempio compatibile con somma e prodotto, quindi si possono moltiplicare e sommare congruenze fra polinomi.

Un caso particolare si ha se il polinomio h(x) è un polinomio costante della forma h(x)=n con n>1.

In questo caso è facile verificare che, se a

,b

sono rispettivamente i coefficienti (dello stesso grado) di f(x), g(x) si ha f(x) g(x) (mod n) se e solo se a

 b

(mod n) per ogni i, dunque la congruenza fra polinomi si riconduce in questo caso alle congruenze aritmetiche fra le coppie di coefficienti numerici dei polinomi.

Teorema.

Dato un numero naturale n>1, ed un qualunque naturale a coprimo con n , si ha:

n è primo  (x+a)

 x

+a (mod n).

Dimostrazione.

() Sia n primo. Sviluppando con la regola di Newton si ha : (x+a)

=

n i

x i a

 n



 

 





0

Confrontando i coefficienti dei polinomi (x+a)

, x

+a (che hanno entrambi il coefficiente principale

=1) la tesi è che sia: _



 



 i

n a

 0 (mod n) per i=1,2,…,n-1; a

 a (mod n).

La prima proprietà deriva dall’osservazione fatta sopra : _



 



 i

n è multiplo di n per i=1,2,…,n-1.

Il fatto che a

 a (mod n) deriva dal piccolo teorema di Fermat a

 1 (mod n), moltiplicando ambo i membri per a.

() Per ipotesi sia (x+a)

 x

+a (mod n), ossia:

_



 



 i

n a

 0 (mod n) per i=1,2,…,n-1; a

 a (mod n).

Supponiamo per assurdo che n non sia primo, e sia q un divisore primo di n, con 1<q<n; sia poi q

la massima potenza di q che divide n (con k>0).

Consideriamo il coefficiente binomiale _



 



 q

n = ^{n(n- 1 )...(n-q} _q! ^{ 1 )} ; si ha:

q! _



 



 q

n = n(n-1)…..(n-q+1).

L’ipotesi _



 



 q

n a

 0 (mod n) implica che q

è divisore del prodotto _



 



 q

n a

, ma q non divide a

(perché q non divide a, essendo a,n coprimi): dunque, per la fattorizzazione unica, q

è divisore di

 

 



 q n .

Essendo qq!, q

n si ha che q

è divisore di q! _



 



 q

n = n(n-1)…..(n-q+1), dunque (essendo q

la massima potenza di q che è divisore di n) per la fattorizzazione unica q é divisore di uno dei fattori (n-i) con 1 i q-1, contraddizione perché, essendo qn, si avrebbe qi con 1 i  q-1.

Nota: come si vede nella dimostrazione, nell’implicazione () si può omettere l’ipotesi che a,n siano coprimi, poiché la congruenza a

 a (mod n) è valida anche se a,n non sono coprimi (cioè se il primo n è divisore di a), in quanto ovviamente n sarà in questo caso anche divisore della differenza a

-a .

In base all’ultimo teorema si può allora implementare il seguente test di primalità, con input n >1:

1) si fissa a piacere un intero a, con 1 a  n-1

2) se mcd(a,n)=d >1 allora si esce con output “n è composto”

3) se invece a,n sono coprimi: se (x+a)

 x

+a (mod n) si esce con output “n è primo”, altrimenti si esce con output “n è composto”

Dimostriamo che tale test è deterministico. Se l’input n è primo, nel passo 2) a,n sono coprimi (le essendo a<n) e nel passo 3) si esce con output “n è primo” per il Teorema precedente. Viceversa, se nell’algoritmo si esce con output “n è primo”, nel passo 2) si deve avere a,n coprimi, dunque nel passo 3) (visto l’output) la congruenza fra polinomi è verificata, ed n è primo per il Teorema precedente.

Esaminiamo la complessità di calcolo dell’algoritmo. Sia x=L(n) la lunghezza binaria di n . Nel passo 2) si usa l’algoritmo euclideo delle divisioni successive, di complessità polinomiale.

Nel passo 3) si deve verificare la congruenza polinomiale (x+a)

 x

+a (mod n), la quale comporta

la verifica delle congruenze dei singoli coefficienti dei 2 polinomi (x+a)

, x

+a : essi sono

polinomi di grado n, e (a parte il coefficiente di grado massimo che è =1 in entrambi) si tratta di

verificare n congruenze numeriche, ognuna di complessità non superiore al polinomiale rispetto a

x=L(m). Ma il numero di tali congruenze è n, quindi di ordine esponenziale O(2

), perciò

l’algoritmo non è “efficiente”.

L’idea di Agrawal, Kayal, Saxena per rendere “efficiente” il precedente test di primalità fu quella di

“diminuire” in qualche modo il grado dei polinomi (x+a)

, x

+a , rendendo tale grado <r con un opportuno r ≤ x

(per un naturale opportuno k): in tal modo verificare la congruenza polinomiale del passo 3) equivale a verificare un numero di congruenze di ordine non superiore al polinomiale rispetto a x=L(m).

Tornando alle congruenze polinomiali, un altro caso particolare della congruenza modulo h(x) si ha se h(x)=x

-1, con r>0.

In tale caso se x

è una qualunque potenza di x ad esponente intero k 0, e se dividiamo k per r con quoziente q e resto t, si ottiene k=rq+t, con 0 t < r, da cui x

-x

=x

x

-x

=x

(x

-1), e tenendo conto che x

-1x

-1 (per le solite identità considerate più volte) si conclude che x

 x

(mod x

-1).

Dunque, per la compatibilità della congruenza con somma e prodotto, dato un polinomio qualunque f(x)=a

+a

x

a

x

a coefficienti interi relativi, si ha

f(x)  

 n i

t i

x

a

1

(mod x

-1)

dove ogni t

é il resto della divisione dell’esponente i per r, cioè ogni t

=imodr, la riduzione di i modulo r : si devono poi sommare nel secondo membro i monomi simili, ossia quelli per cui i resti t

sono uguali.

Il polinomio h(x)= 

 n i

t i

x

a

1

è di grado <r, ed è l’unico polinomio di grado <r tale che f(x) h(x) (mod x

-1),: infatti se si ha f(x) k(x) (mod x

-1), con k(x) di grado <r, allora h(x) k(x) (mod x

-1), dunque h(x)-k(x) è multiplo di x

-1, ed h(x)-k(x) è il polinomio nullo (altrimenti sarebbe di grado <r e multiplo di x

-1, contraddizione), dunque h(x)=k(x).

Questo unico polinomio h(x) di grado <r tale che h(x) f(x) (mod x

-1) è detto riduzione di f(x) modulo x

-1, ed è indicato con f(x)mod(x

-1): come visto esso si ottiene da f(x) riducendo modulo r tutti gli esponenti dell’indeterminata x e sommando i monomi simili: in pratica se f(x)=a

+a

x

+

a

x

si ha f(x)mod(x

-1)=c

+c

x

c

x

dove c

= 

i(mod r)

j

a

.

Esempio: la riduzione modulo x

-1 del polinomio f(x)=5+2x+7x

+11x

+3x

si ottiene riducendo tutti gli esponenti modulo 3:

f(x)mod(x

-1) = 5+2x+7x

+11x+3x

= 5+13x+10x

(per esempio il coefficiente di indice i=1 nella riduzione si ottiene sommando i coefficienti di f(x) di indici j1 (mod 3): 13=2+11).

L’idea di Agrawal, Kayal, Saxena fu di sostituire la verifica della congruenza:

(x+a)

 x

+a (mod n)

che comportava il calcolo di n congruenze aritmetiche, con quella della congruenza : (x+a)

mod(x

-1) (x

+a)mod(x

-1) (mod n)

per un opportuno r (che comportava il calcolo di un numero r di congruenze aritmetiche, essendo i 2 polinomi di grado < r) dove r ≤ x

(per un naturale opportuno k).

Osservazione: se f(x) k(x) (mod n) allora anche f(x)mod(x

-1) h(x)mod(x

-1) (mod n). Infatti, come già notato, il generico coefficiente a

della riduzione modulo (x

-1) di un polinomio (con i=0,1,…,r-1) si ottiene sommando i coefficienti del polinomio che hanno indici congrui ad i modulo r, quindi se i coefficienti di eguale indice in f(x), k(x) sono fra loro congrui modulo n, lo stesso avviene per i coefficienti delle riduzioni modulo (x

-1), per la compatibilità della somma con la congruenza modulo n.

Purtroppo non è vero il viceversa: f(x)mod(x

-1) h(x)mod(x

-1) non implica f(x) k(x) (mod n).

Quindi l’algoritmo di primalità sopra illustrato deve essere fortemente modificato per restare valido.

Il test di primalità AKS si basa sul seguente risultato (di cui diamo solo l’enunciato):

Teorema AKS.

Siano r,n numeri naturali, con n >2, ed r coprimo con n, tale che:

1) ord

n > (log

n)

(dove ord

n=ord([n]

) indica il periodo di [n]

nel gruppo Z

*)

2) per ogni intero a con 1 a  ( ^r ) log

ⁿ (dove  ^{( ) r} è la funzione di Eulero) si abbia:

(x+a)

mod(x

-1) (x

+a)mod(x

-1) (mod n) 3) n ha un divisore primo p>  ( ^r ) log

ⁿ

Allora n è necessariamente una potenza di p.

Il test AKS si implementa nel modo seguente, dato in input un naturale n>2:

1) si testa se n è una potenza di base naturale con opportuno esponente naturale >1 e in caso affermativo si esce con output “n è composto”

2) Si cerca un naturale r coprimo con n tale che ord

n > (log

n)

3) Se esiste un divisore d di n, con d<n, nell’intervallo [2,  ( ^r ) log

ⁿ ] si esce con output “n è composto”

4) Se per ogni naturale a con 1 a   ( ^r ) log

ⁿ si ha:

(x+a)

mod(x

-1) (x

+a)mod(x

-1) (mod m)

si esce con output “n è primo”, altrimenti si esce con output “n è composto”.

Verifichiamo prima di tutto che il test AKS è un test di primalità deterministico, quindi che un input n supera il test se e solo se n è primo.

Sia dunque n >2 primo. Il passo 1) viene superato da n, in quanto, essendo primo, non è potenza di base naturale con esponente naturale opportuno >1.

Il passo 3) viene superato da n in quanto n non ha divisori propri diversi da 1 e da n.

Infine nel passo 4) si esce certamente con output “n è primo” come conseguenza dell’implicazione () dell’ultimo teorema dimostrato (prima del Teorema AKS) in cui abbiamo notato che l’ipotesi a,n coprimi era superflua: infatti da tale implicazione segue (x+a)

 x

+a (mod n) e dunque a maggior ragione (x+a)

mod(x

-1) (x

+a)mod(x

-1) (mod m) (vedere osservazione prima del Teorema AKS).

Viceversa per assurdo supponiamo che n superi il test AKS ma n non sia primo, e sia p un divisore primo di n, con p<n.

Poiché n supera il passo 1), si ha che n non è potenza di base naturale con esponente naturale >1.

Poiché n supera il passo 3), il divisore primo p è >  ( ^r ) log

ⁿ e per il Teorema AKS si conclude

che n è potenza di p, con esponente naturale >1 (perché p<n), in contraddizione con il superamento

del passo 1).