Se n,m sono naturali >1 coprimi, si ha (nm)=(n)(m)

Teoria dei numeri e Crittografia: lezione del 12 dicembre 2011 Numeri perfetti.

Un numero naturale n>1 è detto perfetto se n coincide con la somma dei suoi divisori <n.

Per esempio n=6 è perfetto in quanto 6=1+2+3; n=8 non è perfetto in quanto 81+2+4.

Se per ogni naturale n>1 definiamo la funzione (n) uguale alla somma di tutti i divisori di n (incluso n), si ha che un naturale n>1 è perfetto se e solo se (n)=2n.

Se n è un naturale >1, e se la fattorizzazione di n in prodotto di potenze di primi distinti è:

n=p p₁^k1 ₂^k2....p_r^kr (pi primi distinti, ki >0)

allora (per la fattorizzazione unica) ogni divisore d di n ha la forma:

d=p p₁^h1 ₂^h2....p_r^hr con 0  hi  ki per ogni i=1,….,r dunque si ha la seguente formula per il calcolo di (n):

(n) = ^{11 2 2}

1 0

.... ^r

i i

r h h h

r h ki

p p p

 



Teorema.

Se n,m sono naturali >1 coprimi, si ha (nm)=(n)(m).

Dimostrazione:

Se le fattorizzazioni di n,m in prodotto di potenze di primi distinti sono rispettivamente:

n=p p₁^k1 ₂^k2....p_r^kr m=p_r1^kr1p_r2^kr2....p_s^ks

(i fattori primi di n sono distinti da quelli di m perché n, m sono coprimi) la fattorizzazione di nm in prodotto di potenze di primi distinti è:

nm=p p₁^k1 ₂^k2....p p_r^kr _r1^kr1p_r2^kr2....p_s^ks e per la proprietà distributiva si ottiene:

(n)(m)= ₁ ¹¹ ₁ ^{1 1}

0 0

( .... ^r)( ^r .... ^s)

i i i i

r s

h

h h h

r r s

i i r

h k h k

p p p_ ^ p

  

   

  ₌ ^{11 2 2}

0 1

.... ^s

i i

s h h h

r ih k

p p p

 

 _=(nm).

Vedremo che vi è uno stretto legame fra la teoria di numeri perfetti e quella dei numeri di Mersenne.

Cominceremo con la dimostrazione del seguente risultato di Euclide:

Teorema (Euclide).

Se il numero di Mersenne Mk=2^k-1 è primo (quindi con k necessariamente primo), il numero:

n=2^k-1(2^k-1)=2^kMk

è perfetto (e ovviamente pari).

Dimostrazione.

Essendo Mk dispari, i numeri 2^k-1, Mk sono coprimi, e per un risultato precedente si ha:

(n)=(2^k-1)(Mk).

Essendo Mk primo si ha (Mk)=1+Mk=1+(2^k-1)= 2^k.

I divisori di 2^k-1 sono le potenze 2⁰, 2¹, …., 2^k-1, dunque (2^k-1)= 2⁰+2¹+2²+….+2^k-1=2^k-1(dove si è sfruttata l’identità (x^k-y^k)=(x-y)(x^k-1+x^k-2y+….+xy^k-2+ y^k-1) per x=2, y=1).

In totale si ottiene (n)=2^k(2^k-1)=2[2^k-1(2^k-1)]=2n ed n è perfetto.

Eulero dimostrò il viceversa:

Teorema (Eulero).

Se n è un numero naturale pari perfetto, allora n è della forma n=2^k-1Mk dove Mk=2^k-1 è un numero di Mersenne primo (quindi con k necessariamente primo).

Dimostrazione:

Poiché n è pari, se 2^t (con t>0) è la massima potenza di 2 che divide n, si può scrivere n=2^tm con m dispari.

Poniamo k=t+1>1, in modo che n=2^k-1m.

Essendo m dispari, i numeri 2^k-1, m sono coprimi, e dunque (n)=(2^k-1)(m).

Come nella dimostrazione del Teorema precedente si ha (2^k-1)=2^k-1.

Poiché n è perfetto per ipotesi, si ottiene 2^km=2n=(n)=(2^k-1)(m)=(2^k-1)(m).

Dunque 2^k-1 è divisore del prodotto 2^km; ma 2^k, 2^k-1 sono coprimi (perché consecutivi), quindi 2^k-1 è divisore del fattore m, e si ha m=(2^k-1)M, con M naturale divisore di m.

Sostituendo si ha: 2^km=2^k(2^k-1)M=(2^k-1)(m), da cui (m)=2^kM.

Si ha allora m+M=(2^k-1)M+M=2^kM=(m).

Essendo m,M entrambi divisori di m, ed essendo (m) la somma di tutti i divisori di m, concludiamo che m,M sono gli unici divisori di m (e dunque necessariamente M=1), ossia m è primo ed inoltre:

m=(2^k-1)M=(2^k-1)=Mk, ed n=2^k-1m=2^k-1Mk, come voleva la tesi.

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^k-1(2^k-1)=2^k-1Mk dove Mk è 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.

Per esempio per k=2,3,5 si hanno i numeri di mersenne primi M2=3, M3=7, M5=31 e in corrispondenza i numeri perfetti 6, 28, 496.

E’ invece ancora aperta la seguente 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 =n n( 1)...(n i 1) i!

  

dunque i! _



 



 i

n = n(n-1)…..(n-i+1), ossia il numero primo n è

divisore del prodotto i! _



 



 i

n , e poiché n non è divisore di i! (che è prodotto 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.

Per esporre tale test definiremo il concetto di congruenza polinomiale.

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 ai ,bi sono rispettivamente i coefficienti (dello stesso grado) di f(x), g(x) si ha f(x) g(x) (mod n) se e solo se ai  bi (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)ⁿ = ^{i n-i}

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^n-1 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^k 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^q  0 (mod n) implica che q^k è divisore del prodotto _



 



 q

n a^q, ma q non divide a^q (perché q non divide a, essendo a,n coprimi): dunque, per la fattorizzazione unica, q^k è divisore di



 



 q n .

Essendo qq!, q^kn si ha che q^k+1 è divisore di q! _



 



 q

n = n(n-1)…..(n-q+1), dunque (essendo q^k 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:



 



 i

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

ognuna di complessità polinomiale rispetto a x=L(n). Ma il numero di tali congruenze è n, quindi di ordine esponenziale O(2^x), perciò l’algoritmo non è “efficiente”.

L’idea di Agrawal, Kayal, Saxena per rendere “efficiente” il precedente test di primalità fu quella di sostituire i polinomi (x+a)ⁿ, xⁿ+a , con polinomi di grado minore, e in particolare di grado che fosse di ordine polinomiale rispetto ad x=L(n): in tal modo verificare la congruenza polinomiale coinvolta nel passo 3) equivale a verificare un numero di congruenze aritmetiche di ordine polinomiale rispetto a x=L(n), e la complessità del test diventa globalmente polinomiale.