Teoria dei numeri e Crittografia: lezione del 5 maggio 2011 Lemma. Sia a un elemento di periodo n>1 nel gruppo moltiplicativo G (dunque le potenze distinte di a sono a

Teoria dei numeri e Crittografia: lezione del 5 maggio 2011 Lemma.

Sia a un elemento di periodo n>1 nel gruppo moltiplicativo G (dunque le potenze distinte di a sono a

,a

,…,a

).

Allora fra le potenze distinte di a quelle di periodo n sono tutte e sole le potenze a

con 1in-1 ed i,n coprimi (in particolare esse sono in numero di (n)) .

Dimostrazione:

Notiamo che a

=1

ha periodo 1n, dunque le potenze di periodo n sono da ricercare fra le potenze a

con 1in-1.

Se a

ha periodo n, poniamo d=mcd(i,n): ovviamente i/d, n/d sono numeri naturali.

Si ottiene:

(a

)

= (a

)

= 1

= 1

Per una proprietà del periodo n dell’elemento a

, si ha che l’esponente n/d è multiplo di n, cioè n/d

= nk, con k numero naturale, da cui dk=1, d=1 e si ha la tesi che i,n sono coprimi.

Viceversa supponiamo i,n coprimi. La tesi è che a

ha periodo n. Sia c il periodo di a

: è il minimo esponente positivo tale che (a

)

= a

=1

.

Per una proprietà del periodo n dell’elemento a, si ha che l’esponente ic è multiplo di n: ma i,n coprimi ed nic implicano nc, in particolare nc. D’altronde (a

)

=(a

)

= 1

= 1

, ed essendo c il periodo dell’elemento a

si ha cn.

In totale n=c=ord(a

) e si ha la tesi.

Teorema.

Sia G un gruppo (moltiplicativo) ciclico finito di cardinalità n>1 e sia aG un generatore di G.

Allora fra gli elementi distinti di G , che sono per ipotesi le potenze distinte di a:

a

,a

,…,a

si ha che un generico a

è generatore di G se e solo se 1in-1 ed i,n sono coprimi.

In particolare il numero dei generatori di G è (n) (funzione di Eulero di n).

Dimostrazione:

Basta applicare il Lemma, ricordando che un generatore di G non è altro che un elemento di periodo n=G.

Esempio.

Nel gruppo moltiplicativo ciclico Z

*= {[1], [2], [3], [4]} si è visto in un esempio precedente che a=[2] è un generatore : poiché la cardinalità è 4, tutti e soli i generatori saranno le potenze a

con 1i3 ed i,4 coprimi, cioè le potenze a

=[2], a

=[8]=[3].

Se il gruppo moltiplicativo Z

* è ciclico per un certo valore di n>1, e se [a] è un generatore, essendo (n) la cardinalità di Z

*, tutti e soli i generatori saranno le potenze [a]

= [a

], dove 1i(n)-1, e i,(n) sono coprimi, ed essi sono in numero di ((n)).

In particolare, se a è una radice primitiva modulo n (sempre che essa esista), le radici primitive modulo n sono tutte e sole le riduzioni a

modn, dove 1i(n)-1, e i,(n) sono coprimi, ed esse sono in numero di ((n)).

Anelli, campi e polinomi.

Un anello è insieme non vuoto A in cui sono definite 2 operazioni (indicate rispettivamente con i simboli di somma e prodotto) tali che:

- A(+) é gruppo commutativo

- A(×) é un semigruppo (cioè vale la proprietà associativa del prodotto)

- valgono le proprietà distributive: per ogni a,b,cA si ha a(b+c)=ab+ac, (b+c)a=ba+ca In un anello A vale la seguente proprietà (se 0

indica :

per ogni aA, si ha 0

a=a0

=0

(infatti per esempio 0

+0

a=0

a=(0

+0

)a=0

a+0

a e basta usare la legge di cancellazione valida nel gruppo A(+)per ottenere 0

a=0

).

In un anello A si può definire il concetto di divisore: dati a,bA si dice che a è divisore di b o che b è multiplo di a (e si scrive il simbolo ab) se esiste cA tale che b=ac.

Un anello A è detto commutativo se il prodotto soddisfa la proprietà commutativa; è detto con unità se esiste l’elemento neutro del prodotto (indicato con 1

).

Sono esempi di anelli commutativi con unità: l’anello degli interi relativi, l’anello dei numeri razionali relativi, l’anello dei numeri reali relativi.

Anche l’insieme Z

rispetto alla somma e prodotto di classi di congruenza è un anello commutativo con unità.

Se A è un anello con unità, rispetto al prodotto è un monoide, dunque si può considerare il gruppo moltiplicativo A* degli elementi invertibili di A rispetto al prodotto.

Un anello commutativo con unità A è detto campo se ogni elemento aA, a0

ha inverso in A rispetto al prodotto. In tale caso il gruppo A*= A-{0

} è un gruppo commutativo.

Sono esempi di campi: il campo dei numeri razionali e il campo dei numeri reali. L’anello dei numeri interi relativi non è un campo, perché gli unici elementi invertibili sono 1, -1.

Teorema.

In un campo A vale la legge di annullamento del prodotto: comunque dati a,bA, se ab=0

si ha a=0

oppure b=0

(equivalentemente se a,b0

allora ab0

).

Dimostrazione:

Sia per assurdo ab=0

con a,b0

. Per ipotesi esiste a

A, da cui:

b=1

b=(a

a)b=a

(ab)=a

0

=0

, contraddizione.

Se A è un anello commutativo con unità, ed x è una indeterminata, si può costruire l’insieme A[x]

dei polinomi a coefficienti in A nell’indeterminata x, formato dalle espressioni algebriche della forma: f(x) = a

+a

x+a

x

+….+a

x

dove a

A, m intero ³0.

Il polinomio nullo è quello con tutti i coefficienti =0

. Per un polinomio non nullo f(x) si definisce il grado gr(f(x)) uguale al massimo indice k tale che il coefficiente a

sia 0

: il coefficiente a

è allora detto coefficiente principale o coefficiente direttore di f(x).

Se f(x), g(x) A[x] sono polinomi non nulli di grado rispettivamente n, m e se a

, b

sono rispettivamente i loro coefficienti principali, nell’ipotesi che il prodotto a

b

sia non nullo si ha che esso è il coefficiente principale del polinomio prodotto f(x)g(x), che ha dunque grado n+m.

Fra i polinomi di A[x] si possono definire nel modo usuale una somma e un prodotto di polinomi (sfruttando le operazioni dell’anello A) che rendono A[x] un anello commutativo con unità, come A.

Dato un polinomio f(x)= a

+a

x+a

x

+….+a

x

A[x] ed un elemento aA, si chiama valore assunto da f(x) in a l’elemento f(a)= a

+a

a+a

a

+….+a

a

A ottenuto sostituendo x con a.

Se f(a)=0

si dice che a è radice di f(x).

E’ facile verificare che, se f(x), g(x)A[x], h(x)=f(x)g(x), dato aA, si ha: h(a)=f(a)g(a).

Teorema di Ruffini.

Dato un polinomio f(x)A[x]:

un elemento aA è radice di f(x) Û (x-a)ôf(x).

Dimostrazione:

(Ü) Se esiste h(x)A[x] tale che f(x)=(x-a)h(x), si ha, calcolando il valore in a:

f(a)=0

h(a)=0

(Þ) Per ogni aA ed ogni intero t>0 vale l’identità algebrica (che si può dimostrare direttamente o per induzione su t):

x

- a

= (x-a)(x

+ax

+…..+a

x+a

) dunque (x-a) (x

– a

) per ogni t>0.

Da ciò segue che, se f(x)= a

+a

x+a

x

+….+a

x

, (x-a) é divisore di f(x)-f(a)=a

(x-a)+a

(x

-a

)+…..+a

(x

-a

)

In particolare, se per ipotesi f(a)=0

, (x-a) è divisore di f(x).

Corollario.

Siano A un campo ed f(x) un polinomio non nullo in A[x] di grado n. Il numero di radici distinte di f(x) in A è n.

Dimostrazione:

Siano a

,a

,…,a

A le radici distinte di f(x). Per il Teorema di Ruffini si ha f(x)=(x-a

)g

(x), con g

(x)A[x]. Da 0

=f(a

)=(a

-a

)g

(a

) e da a

-a

0

segue g

(a

)=0

(per la legge di annullamento del prodotto valida nel campo A). Di nuovo per il Teorema di Ruffini si ha g

(x)=(x-a

)g

(x), con g

(x)A[x], da cui f(x)=(x-a

)(x-a

)g

(x). Così procedendo, dopo r passi, si ha:

f(x)=(x-a

)(x-a

)…….(x-a

)g

(x) con g

(x)A[x]

Calcolando i gradi di ambo i membri (utilizzando la regola del grado del prodotto di polinomi) si ha n=r+gr(g(x)), dunque rn, perché gr(g(x))³0.

Sia A un campo: possiamo considerare il gruppo moltiplicativo A*=A-{0

} degli elementi invertibili di A rispetto al prodotto.

Teorema.

Se A è un campo finito, il gruppo moltiplicativo A*=A-{0

} è un gruppo ciclico.

Dimostrazione:

Sia G=A*, ed n=G: la tesi è che esiste un generatore del gruppo G, cioè un elemento aG di periodo = n.

Sia S l’insieme di tutti i naturali divisori di n. Per ogni dS sia S

il sottoinsieme di G formato dagli elementi di G di periodo d (a priori può essere S

=). Supponiamo che S

, e calcoliamo la cardinalità di S

.Fissiamo un elemento a in S

(quindi a ha periodo d): le potenze distinte di a sono in numero di d e sono a

, a

,…,a

. Ognuna di tali potenze è radice del seguente polinomio di grado d: f(x)=x

-1

A[x]; infatti (a

)

=(a

)

=1

. Essendo A un campo, il polinomio f(x) ha in A al più d radici, dunque le d potenze di a esauriscono tutte le radici di f(x) in A.

Ma un elemento qualunque bS

è radice di f(x) (perché b ha periodo d dunque b

=1

) .

Si conclude che ogni elemento di S

è una potenza di a. Per costruzione gli elementi di S

sono le potenze di a che hanno periodo d, dunque, per un risultato precedente sono in numero di (d).

Dunque S

ha cardinalità (d) (se è ). Al variare di dS, i sottoinsiemi S

sono banalmente a due a due disgiunti e la loro unione è G (se yG, detto d il periodo di y, si ha d divisore di n, dS, yS

).

Dunque:

n = ôGô =

d S

S



₌

 S

Per un risultato precedente si ha n= ( )

d n

 d

 ₌

d n

 S _{. Ma ôS}

_{ô=0 (se S}

=) oppure ôS

ô=(d) (se S

). Dall’eguaglianza precedente segue che nessun S

è vuoto (altrimenti 

S

_< ^{( )}

d n

 d

 _{) e in}

particolare S

, ossia esiste un elemento in G di periodo n, e si ha la tesi.

Nota: La dimostrazione precedente non è costruttiva, perché non fornisce un algoritmo per il calcolo di un generatore del gruppo A* .

Lemma.

Dato un intero n>1:

l’anello commutativo con unità Z

è campo Û n è primo Dimostrazione:

Ricordiamo che in Z

una classe [a][0] ha inverso se e solo se a,n sono coprimi.

(Þ) Se per assurdo n non fosse primo, esisterebbe un divisore non banale d di n con 1<d<n, e la classe [d][0] non avrebbe inverso (essendo mcd(d,n)=d>1) contro l’ipotesi che Z

è campo

(Ü) Le classi [0] in Z

sono [1],[2],..,[n-1] ed essendo n coprimo con tutti i numeri 1,2,…,n-1 (perché essi non sono multipli di n ed n è primo) tutte queste classi hanno inverso, quindi Z

è campo.

Come conseguenza dei risultati precedenti:

Teorema di Gauss (il caso n primo).

Se n è primo, il gruppo moltiplicativo Z

* è ciclico (quindi esiste qualche radice primitiva modulo n).

Dimostrazione:

Segue immediatamente dai 2 Teoremi precedenti..

Nota: La dimostrazione dell’esistenza di un generatore per il gruppo moltiplicativo A* di un campo finito A non è costruttiva, dunque in particolare non fornisce un algoritmo per calcolare una radice primitiva modulo n, quando n è primo: a tutt’oggi non è noto nessun algoritmo di complessità non più che polinomiale che risolva il problema.

In ogni caso, se n è primo, sappiamo che il numero di radici primitive modulo n è ((n))=(n-1).

Per esempio se n=11, il numero di radici primitive modulo 11 è ((11))=(10)=4: se a è una di esse, tutte le radici primitive modulo 11 sono della forma a

mod11, dove 1i(11)-1=9, con i,10 coprimi, ossia i=1,3,7,9.

Teorema di Gauss (il caso del quadrato di un numero primo).

Se n=p

con p primo, il gruppo moltiplicativo Z

* è ciclico (quindi esiste qualche radice primitiva modulo n).

Dimostrazione.

Poiché tratteremo di classi di congruenza con diversi moduli, conveniamo di indicare, per un generico modulo m>1, la classe di congruenza rappresentata dall’intero a modulo m con [a]

. Sia a una radice primitiva modulo p (che esiste per il risultato precedente): (p)=(p-1) è il periodo di [a]

nel gruppo moltiplicativo Z

* quindi (p-1) è il minimo esponente positivo tale [a]

=[1]

cioè tale che a

1 (mod p) . Vi sono 2 casi possibili:

1) a

non è congruo 1 modulo n

2) a

è congruo 1 modulo n

Supponiamo che si verifichi il caso 1): sia d il periodo di [a]

nel gruppo moltiplicativo Z

*: per una proprietà del periodo si ha dô(n) cioè dôp(p-1), dunque p(p-1)=hd con h numero naturale.

Essendo a

1 (mod n=p

), a maggior ragione si ha a

1 (mod p), dunque [a]

=[1]

e per una proprietà del periodo di [a]

in Z

* si deduce che (p-1)ôd, dunque d=(p-1)s con s numero naturale.

Da p(p-1)=hd=h(p-1)s segue p=hs, quindi s=1 oppure s=p. Ma non può essere s=1, altrimenti sarebbe d=(p-1), a

1 (mod n), in contraddizione con l’ipotesi del caso 1).

Dunque s=p, d=p(p-1): il periodo di [a]

nel gruppo moltiplicativo Z

* è allora d=(n)=p(p-1), e l’intero a è una radice primitiva modulo n.

Tratteremo il caso 2) nella prossima lezione.