Un elemento neutro in A è un elemento eA tale che per ogni aA si ha ae = ea=a

Teoria dei numeri

Lezione del giorno 2 aprile 2009 Insiemi dotati di operazione.

Dato un insieme A non vuoto, una operazione in A è una funzione f: AxA  A che associa ad ogni coppia (a,b)A di operandi un unico risultato f(a,b)A (indicato anche con a^b).

L’operazione soddisfa la proprietà associativa se per ogni a,b,cA si ha (a^b)^{c= a}^(b^c).

L’operazione soddisfa la proprietà commutativa se per ogni a,bA si ha a^{b = b}^a.

Un elemento neutro in A è un elemento eA tale che per ogni aA si ha a^{e = e}^a=a.

Se vale la proprietà associativa A è un semigruppo; un semigruppo in cui esiste un elemento neutro è un monoide,

Se A è un monoide con neutro eA, un elemento aA è simmetrizzabile se esiste a’A (detto simmetrico di a) tale che a^{a’ = a’}^a=e.

Un gruppo è un monoide in cui tutti gli elementi sono simmetrizzabili.

Se A è un monoide, l’insieme A* di tutti gli elementi simmetrizzabili è non vuoto (contiene almeno il neutro di A) ed è un gruppo rispetto alla stessa operazione di A.

Useremo spesso la notazione moltiplicativa ab oppure ab per indicare il risultato dell’operazione (in questo caso il neutro sarà detto unità e indicato con 1A, il simmetrico di a sarà detto inverso di a e indicato con a^-1), oppure la notazione additiva a+b (in questo caso il neutro sarà detto zero e indicato con 0A, il simmetrico di a sarà detto opposto di a e indicato con –a).

Esempi.

L’insieme N dei naturali è semigruppo commutativo rispetto alla somma e monoide commutativo rispetto al prodotto.

L’insieme Z degli interi relativi è gruppo commutativo rispetto alla somma e monoide commutativo rispetto al prodotto: in questo caso il gruppo degli elementi invertibili è Z*={1,-1}.

L’insieme Q dei razionali relativi (rispettivamente R dei reali relativi) è gruppo commutativo rispetto alla somma e monoide commutativo rispetto al prodotto: in questo caso il gruppo degli elementi invertibili è Q*= Q -{0} (rispettivamente R*= R -{0}).

Operazioni in Zm

Fissato il modulo m>1, nell’insieme Zm={[0],[1],…,[m-1]} delle classi di congruenza modulo m si possono definire le operazioni di somma e prodotto ponendo per ogni [a], [b]Zm:

[a] + [b] = [a+b] [a][b] = [ab]

L’unicità dei risultati, indipendenti dai rappresentanti a,b delle classi, è facile da verificare: se [a]=[c], [b]=[d] allora ac (mod m), bd (mod m), da cui a-c=km, b-d=hm (con h,kZ), e si deduce (a+b)-(c+d)=(h+k)m,ab-cd=(kb+hc)m,a+bc+d (mod m), abc+d (mod m), [a+b]=[c+d], [ab]=[cd].

Rispetto alla somma Zm è gruppo commutativo (il neutro è [0], l’opposto di [a] è [m-a], perché [a]+

[m-a]=[m]=[0]) e rispetto al prodotto è monoide commutativo (il neutro è [1]).

Se rappresentiamo le classi di congruenza [0],[1],…,[m-1]Zm identificandole con i valori numerici 0,1,….,m-1 (per esempio allo scopo di inserirle come dati in un algoritmo implementato al computer), comunque presi i valori a,b=0,1,….,m-1 i risultati delle operazioni di somma e prodotto si ottengono con la riduzione modulo m (la somma è (a+b)modm, il prodotto è (ab)modm).

Con tale rappresentazione numerica delle classi di congruenza, possiamo calcolare la complessità di calcolo delle operazioni in Zm.

Poiché i casi a=0 o b=0 sono banali, possiamo supporre 0<a,b<m. Sia poi k=L(m) la lunghezza (binaria) di m: si ha L(a), L(b)L(m)=k.

Complessità della somma in Zm: sappiamo che la somma a+b dei numeri naturali a,b ha complessità lineare O(k); si ha a+b<2m, dunque L(a+b)L(2m)=L(m)+1=k+1, e dunque la riduzione (a+b)modm (essendo ottenuta come resto della divisione di (a+b) per m) ha complessità O((k+1)²) ossia O(k²). Complessivamente la somma in Zm ha complessità polinomiale O(k²).

Complessità del prodotto in Zm: sappiamo che il prodotto ab dei numeri naturali a,b ha complessità quadratica O(k²); si ha ab<m², dunque L(ab)L(m²)2L(m)=2k, e dunque la riduzione (ab)modm (essendo ottenuta come resto della divisione di (ab) per m) ha complessità O((2k)²) ossia O(k²).

Complessivamente il prodotto in Zm ha complessità polinomiale O(k²).

Non tutti gli elementi di Zm sono invertibili rispetto al prodotto: per esempio [0] certamente non lo è, in quanto [0][x]=[0] per ogni [x] in Zm.

Per quanto riguarda le classi non nulle:

Teorema.

Una classe [a]Zm, con 1am-1, è invertibile rispetto al prodotto se e solo se a,m sono coprimi.

Dimostrazione:

Se [a] è invertibile, esiste [b] tale che [a][b]= [ab]= [1], da cui ab1 (mod m), ab-1=mk, con k intero, 1=ab+m(-k)=combinazione lineare di a,m, da cui 1=mcd(a,m).

Viceversa se 1=mcd(a,m), allora 1=ax+by con x,y interi, ax1 (mod m), [a][x]= [ax]= [1], e [x] è l’inverso di [a].

Dalla dimostrazione precedente si deduce che, se a,m sono coprimi, l’inverso di [a] in Zm è [x], dove x è il coefficiente di a nella rappresentazione di 1 come combinazione lineare di a,m; in particolare l’inverso di [a] si può calcolare con l’algoritmo Euclideo esteso che (essendo a<m) ha complessità polinomiale O(k³) nella lunghezza k dell’input m.

Se identifichiamo le classi di congruenza modulo m con i valori numerici 0,1,….,m-1, l’inverso di a con 1am-1 (se a,m sono coprimi) è la riduzione xmodm dove x è come sopra: trovato x con l’algoritmo Euclideo esteso, si tratta di calcolare xmodm, ma (come notato nella costruzione delle successioni si, ti dell’algoritmo) x è sempre (in valore assoluto) <m, dunque se x>0 si ha xmodm=x, mentre se x<0 si ha xmodm=m-(-x)=m+x, e in ogni caso globalmente l’algoritmo per calcolare l’inverso a^-1=xmodm resta di complessità polinomiale O(k³) nella lunghezza k dell’input m.

Abbiamo dimostrato che le classi invertibili di Zm (rispetto al prodotto) sono tante quanti gli interi a coprimi con m tali che 1am-1, o equivalentemente quanti gli interi a coprimi con m tali che 1am: tale numero, che esprime la cardinalità gruppo Zm* degli elementi invertibili del monoide Zm (rispetto al prodotto), è detto funzione di Eulero dell’intero m>1 ed è indicato con (m).

Esponenziazione modulare

Sia m>1 un intero, fissiamo un esponente intero positivo hm, un elemento [x] in Zm (con 0x<m), e poniamoci il problema di trovare un algoritmo per calcolare la potenza [x^h] (equivalentemente la riduzione x^hmodm).

Esporremo un algoritmo molto efficiente (di complessità polinomiale), detto esponenziazione modulare.

Siano k=L(m), t=L(h) le lunghezze (binarie) del modulo m e dell’esponente h: essendo hm si ha tk. Poiché t rappresenta il numero di cifre binarie di h, si ha:

h=at-12^t-1+ at-22^t-2+….+a12+a0 (con ai=0,1)

Costruiamo una successione y0,y1,...,yt di numeri interi ponendo:

y0=1; per ogni i>0 yi=(y_i1²x^ati)^modm

Ogni elemento della successione yi è una riduzione modulo m, dunque 0≤yi<m; inoltre ogni elemento della successione yi (con i>0) si può calcolare (a partire dal precedente) con la riduzione di due prodotti con fattori <m (il quadrato di yi-1 e il prodotto del risultato per _x^ati, quest’ultimo uguale ad x oppure ad 1, poiché l’esponente at-1 è =0,1), dunque (come visto esaminando la complessità del prodotto in Zm) il calcolo di ogni yi con i>0 ha complessità O(k²); il numero degli elementi della successione da costruire è tk, dunque complessivamente l’algoritmo ha complessità polinomiale O(k³).

Dimostriamo che tale algoritmo fornisce il valore della riduzione x^kmodm: precisamente dimostriamo che si avrà yt= x^kmodn.

Dimostriamo prima per induzione che per ogni i con 1it, si ha:

yi  ^{(a 2 a 2}-i2 ^{. a}ti-1^{2 a}ti-⁾ 2

1 -t 1 -i

x -t ^{   } (mod m) (*)

Si ha y1=(y₀²x^at-1)modm quindi y1_x^at-1(mod m), e la (*) è vera per i=1.

Supponiamo (*) vera per i e dimostriamola per i+1: si hanno le seguenti congruenze modulo m yi+1  (y_i²x^ati-1)^ _x^{[2(a-t12ia -t22-i1.ati-12ati-)a-t-i1]=}_x^{(a-t12ia -t22-i1.ati-2a-t-i1)}

quindi la (*) è vera per i+1.

In particolare, per i=t, si ottiene la congruenza:

yt  x^{(at-12t-1at-22t-2.a12a0)= xk (mod n)}

Poiché, come già notato, si ha 0≤yi<m, la precedente congruenza implica che yt = x^kmodm.

Notiamo che nell’algoritmo anche la grandezza dei numeri coinvolti nei calcoli è limitata: ad ogni passo si moltiplicano fattori <m e si riduce il risultato modulo m, quindi si lavora sempre con numeri <m².

Esempio.

Siano m=341, x=2, e calcoliamo [2³⁴⁰] in Z341.

Si tratta quindi di calcolare con l’esponenziazione modulare la riduzione 2³⁴⁰mod341.

La rappresentazione binaria dell’esponente 340 è:

340 = 12⁸+02⁷+12⁶+02⁵+12⁴+02³+12²+02¹+0 = (101010100)2

Seguendo i passi dell’algoritmo, costruiamo la successione y0,y1,y2,y3,y4,y5,y6,y7,y8,y9 con y0=1 e per i>0 yi=(y_i1²2^a9i )mod341 , dove at-i è la cifra binaria coefficiente di 2^t-i in 340.

Si ha:

y1=(1²2^a8)mod341=2 ; y2=(1²2^a7)mod341=4 ; y3=(4²2^a6)mod341=32 ; y4=(32²2^a5) mod341=1 ;

y5=(1²2^a4)mod341=2 ; y6=(2²2^a3)mod341=4 ; y7=(4²2^a2)mod341=32 ; y8=(32²2^a1) mod341=1 ;

y9=(1²2^a0)mod341=1=2³⁴⁰mod341.

Possiamo allora concludere che [2³⁴⁰]=[1] in Z341.