Teoria dei numeri e Crittografia: lezione del 21 novembre 2011Lemma.Sia a un elemento nel gruppo moltiplicativo G di periodo ord(a)=n>1 (quindi a1

Teoria dei numeri e Crittografia: lezione del 21 novembre 2011 Lemma.

Sia a un elemento nel gruppo moltiplicativo G di periodo ord(a)=n>1 (quindi a1

e 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 ord(a

)=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 ord(a

)=n. Sia c= ord(a

) : c è 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)= 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 modo analogo si ottiene 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.

Si dice che in un anello A vale la legge di annullamento del prodotto se comunque dati a,bA, da ab=0

segue a=0

oppure b=0

(equivalentemente se da a,b0

segue ab0

).

Per esempio nell’anello Z degli interi relativi vale la legge di annullamento del prodotto.

Teorema.

In un campo A vale la legge di annullamento del prodotto.

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

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.

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: vale

dunque in questo caso la regola gr(f(x)g(x))=gr(f(x))+gr((g(x)).

Tale regola vale per esempio se nell’anello A vale la legge di annullamento del prodotto (in particolare se A è un campo, come dimostrato nel Teorema precedente).

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)=(a-a)h(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, valida perché A è un campo) 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 numeri naturali divisori di n:

S = { dN / 1 d n, d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* .