• Non ci sono risultati.

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
1
0
0

Testo completo

(1)

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

L’operazione soddisfa la proprietà associativa se per ogni a,b,cA si ha (ab)c= a(bc).

L’operazione soddisfa la proprietà commutativa se per ogni a,bA si ha ab = ba.

Un elemento neutro in A è un elemento eA tale che per ogni aA si ha ae = ea=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 aa’ = 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.

(2)

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)2) ossia O(k2). Complessivamente la somma in Zm ha complessità polinomiale O(k2).

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

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

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(k3) 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(k3) 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 [xh] (equivalentemente la riduzione xhmodm).

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-12t-1+ at-22t-2+….+a12+a0 (con ai=0,1)

(3)

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

y0=1; per ogni i>0 yi=(yi12xati)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 xati, 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(k2); il numero degli elementi della successione da costruire è tk, dunque complessivamente l’algoritmo ha complessità polinomiale O(k3).

Dimostriamo che tale algoritmo fornisce il valore della riduzione xkmodm: precisamente dimostriamo che si avrà yt= xkmodn.

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

yi (a 2 a 2-i2 . ati-12 ati-) 2

1 -t 1 -i

x -t (mod m) (*)

Si ha y1=(y02xat-1)modm quindi y1xat-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 (yi2xati-1)x[2(a-t12ia -t22-i1.ati-12ati-)a-t-i1]=x(a-t12ia -t22-i1.ati-2a-t-i1)

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

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

ytx(at-12t-1at-22t-2.a12a0)= xk (mod n)

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

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

Esempio.

Siano m=341, x=2, e calcoliamo [2340] in Z341.

Si tratta quindi di calcolare con l’esponenziazione modulare la riduzione 2340mod341.

La rappresentazione binaria dell’esponente 340 è:

340 = 128+027+126+025+124+023+122+021+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=(yi122a9i )mod341 , dove at-i è la cifra binaria coefficiente di 2t-i in 340.

Si ha:

y1=(122a8)mod341=2 ; y2=(122a7)mod341=4 ; y3=(422a6)mod341=32 ; y4=(3222a5) mod341=1 ;

y5=(122a4)mod341=2 ; y6=(222a3)mod341=4 ; y7=(422a2)mod341=32 ; y8=(3222a1) mod341=1 ;

y9=(122a0)mod341=1=2340mod341.

Possiamo allora concludere che [2340]=[1] in Z341.

Riferimenti

Documenti correlati

Verifichiamo che A `e

La forza magnetica si ottiene sostituendo nella espressione della forza magnetica la nuova espressione della corrente che scorre

Altrimenti deve essere hgi = G, ma in tal caso G `e un gruppo ciclico di ordine non primo, e in quanto tale ha certamente dei sottogruppi.. (3) Provare che se G ` e un gruppo tale

[r]

[r]

Quando non è espressamente indicato il contrario, per la soluzione degli esercizi è possibile usare tutti i risultati visti a lezione (compresi quelli di cui non è stata fornita

Si pu` o tradurre fedelmente ogni nozione ed ogni propoosizione espressi nel linguaggio degli spazi vettoriali dall’ambito dei vettori geometrici all’ambito dei vettori numerici

Geometricamente: f e’ iniettiva, suriettiva, biiettiva se e solo se ogni retta parallela all’asse x che interseca B interseca il grafico di f in al piu’ un punto, in almeno un punto,