• Non ci sono risultati.

Dato un insieme A non vuoto, una

N/A
N/A
Protected

Academic year: 2021

Condividi "Dato un insieme A non vuoto, una"

Copied!
5
0
0

Testo completo

(1)

Teoria dei numeri e Crittografia: lezione del 7 novembre 2011 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 (necessariamente unico) è un monoide.

Se A è un monoide con elemento neutro e∈A, un elemento a∈A è simmetrizzabile se esiste a’∈A (detto simmetrico di a, necessariamente unico) 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 oppure semplicemente con 1, 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 oppure semplicemente con 0, il simmetrico di a sarà detto opposto di a e indicato con –a).

Un semigruppo (rispettivamente un monoide, un gruppo) è detto commutativo se l’operazione soddisfa la proprietà commutativa (spesso se si tratta di un gruppo commutativo si usa il termine gruppo abeliano).

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, è garantita dalla compatibilità della congruenza rispetto alle operazioni di somma e prodotto di numeri interi.

Rispetto alla somma Zm è gruppo commutativo (il neutro è [0], l’opposto di [a] è [-a] perché [a]+[-a]=[0]) e rispetto al prodotto è monoide commutativo (il neutro è [1]).

Rappresentazione digitale delle classi di congruenza e complessità delle operazioni

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

(2)

si ottengono con la riduzione modulo m dei risultati di somma e prodotto aritmetici (la somma è (a+b)modm, il prodotto è (ab)modm).

Con tale rappresentazione “digitale” 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 x=L(m) la lunghezza (binaria) di m: si ha L(a), L(b)≤ L(m)=x.

Complessità della somma in Zm: sappiamo che la somma aritmetica a+b dei numeri naturali a,b ha complessità lineare di ordine O(x) (essendo gli addendi di lunghezza ≤ x) ; sappiamo anche che L(a+b)≤ max{L(a),L(b)}+1≤ x+1, e dunque il calcolo della riduzione (a+b)modm (essendo ottenuta come resto della divisione di (a+b) per m) ha complessità quadratica di ordine O(x2).

Complessità del prodotto in Zm: sappiamo che il prodotto aritmetico ab dei numeri naturali a,b ha complessità di ordine quadratico O(x2) (essendo i fattori di lunghezza ≤ x); sappiamo anche che L(ab)≤ L(a)+L(b) ≤ 2x, e dunque il calcolo della riduzione (ab)modm (essendo ottenuta come resto della divisione di ab per m) ha complessità quadratica O(x2).

Complessità del calcolo dell’opposto in Zm: dato a in Zm (con 0≤ a<m) per calcolare l’opposto rispetto alla somma (escludendo il caso banale a=0) si deve calcolare la riduzione (-a)modm che coincide con la sottrazione m-a, dunque tale algoritmo ha complessità lineare di ordine O(x) (dove x=L(m)).

Per calcolare la complessità del calcolo dell’inverso in Zm, notiamo che non tutti gli elementi del monoide 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 sussiste il seguente risultato:

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 relativo, 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], ossia [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=mcd(a,m) come combinazione lineare di a,m.

Nella rappresentazione digitale degli elementi di Zm, se identifichiamo le classi di congruenza modulo m con i valori numerici 0,1,….,m-1, fissato a con 1≤ a≤ m-1 troviamo la complessità di calcolo dell’inverso di a in Zm (se a,m sono coprimi).

Possiamo utilizzare l’algoritmo Euclideo esteso applicato ai numeri m, a : dopo avere eseguito n divisioni successive (per verificare che 1=mcd(m,a)), si costruiscono le successioni di interi non negativi si ,ti con i=0,1,….,n+1, e si ha 1=m⋅(-1)nsn+a⋅(-1)n+1tn .

Per quanto osservato sopra, la classe di congruenza [(-1)n+1tn] è l’inverso della classe [a] : dunque l’inverso di a (come elemento di Zm) è la riduzione [(-1)n+1tn]modm.

Ma ricordiamo che (come visto nell’esame della complessità dell’algoritmo Euclideo esteso), tutti i termini delle 2 successioni costruite sono non superiori al maggiore dei 2 numeri m, a quindi in

(3)

particolare 0≤ tn≤ m. Notiamo anche che 0< tn< m (nei casi tn=0,m si ottiene che l’inverso di [a] è [0] , contraddizione). Dunque vi sono 2 casi:

- se il numero n delle divisioni effettuate è dispari, allora (-1)n+1tn= tn con 0< tn< m, e dunque l’inverso di a (come elemento di Zm) è tn

- se il numero n delle divisioni effettuate è pari, allora (-1)n+1tn= -tn , l’inverso di a (come elemento di Zm) è m - tn .

In ogni caso per calcolare l’inverso di a, si è eseguito l’algoritmo Euclideo esteso (di complessità cubica di ordine O(x3)) e (al più) la sottrazione m - tn (di complessità lineare di ordine O(x)).

In totale l’inverso di a∈Zm (se esiste) si può calcolare con un algoritmo di complessità cubica di ordine O(x3).

La funzione di Eulero.

Abbiamo dimostrato che, fissato il modulo m>1, 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 (essendo m>1 il numero m non è coprimo con sé stesso, dunque il range di a può estendersi al valore a=m senza che nulla cambi in sostanza): 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).

Calcoliamo la funzione di Eulero di m nel caso particolare in cui m sia la potenza di un numero primo.

Osserviamo che, se m=pk con p primo e k>0, un numero naturale a non è coprimo con m se e solo se a è multiplo di p: infatti se mcd(a,m)=d>1, essendo dpk si ha d=ph con 0<h≤ k (per la fattorizzazione unica) da cui pd e per transitività pa; viceversa se pa allora, posto d=mcd(a,pk), si ha ppk , pa, dunque pd e si conclude che d>1 .

Dunque, per calcolare ϕ(pk), dobbiamo sottrarre al numero pk (di tutti i naturali compresi fra 1 e pk) il numero di tutti quelli che sono multipli di p: poiché i multipli di p (compresi fra 1 e pk) sono in numero di m/p=pk-1, si ottiene la formula per il calcolo della funzione di Eulero per potenze di primi:

ϕ(pk)=pk-pk-1=pk-1(p-1)

In particolare se m=p primo, si ha:

ϕ(p)=p-1.

Teorema.

Se m,n>1 sono numeri naturali coprimi si ha ϕ(mn) = ϕ(m)ϕ(n) (dove ϕ è funzione di Eulero).

Dimostrazione:

Definiamo la funzione f: Zmn → Zm x Zn ponendo f([x]mn) = ([x]m , [x]n) .

La f è surgettiva: infatti per ogni coppia ([a]m ,[b]n)∈ Zm x Zn il Teorema Cinese del Resto assicura l’esistenza di qualche soluzione intera del sistema:

(mod ) (mod )

x a m

x b n

 ≡

 ≡

e si ha f([x]mn) = ([x]m , [x]n)= ([a]m , [b]n).

Avendo dominio e codominio stessa cardinalità mn, la f è biunivoca.

Si può verificare che una classe [a]mn è invertibile in Zmn se e solo se la classe [a]m é invertibile in Zm e la classe [a]n é invertibile in Zn : infatti se [a]m é invertibile in Zm, esiste un interob tale che [a]mn[b]mn=[ab]mn=[1]mn, da cui ab≡1 (mod mn), ab≡1 (mod m) e ab≡1 (mod n) ossia [a]m[b]m=[ab]m=[1]m e [a]n[b]n=[ab]n=[1]n e si conclude che [a]m é invertibile in Zm e [a]n é invertibile in Zn ; viceversa se [a]m é invertibile in Zm e [a]n é invertibile in Zn, esistono interi b, c tali che [a]m[b]m=[ab]m=[1]m e [a]n[c]n=[ac]n=[1]n da cui ab≡1 (mod m) e ac≡1 (mod n), ma il

(4)

Teorema Cinese del Resto assicura l’esistenza di un intero d tale che d≡b (mod m) e d≡c (mod n), da cui ad≡1 (mod m) e ad≡1 (mod n), m(ad-1), n(ad-1), mn(ad-1) (perché m, n sono coprimi) e si conclude che [a]mn[d]mn=[ad]mn=[1]mn ossia [a]mn è invertibile in Zmn .

Dunque la restrizione di f al gruppo Zmn* fornisce una funzione biunivoca fra Zmn* e Zm*x Zn* , da cui si conclude che ϕ(mn) =  Zmn* = Zm*x Zn*= Zm* Zn*= ϕ(m)ϕ(n) .

Osservazione. Il Teorema precedente si può estendere facilmente per induzione al caso di più di 2 numeri naturali: se m1,m2,….,mn sono numeri naturali >1 a 2 a 2 coprimi, si ha:

ϕ(m1m2…mn)= ϕ(m1) ϕ(m2)… ϕ(mn).

Basta infatti procedere per induzione con base n=2 utilizzando (come nella dimostrazione del Teorema Cinese del Resto) l’osservazione che se m1,m2,….,mn, mn+1 sono a 2 a 2 coprimi anche (m1m2….mn), mn+1 sono coprimi, dunque se ϕ(m1m2…mn)= ϕ(m1) ϕ(m2)… ϕ(mn) allora:

ϕ(m1m2…mnmn+1)= ϕ((m1m2…mn)mn+1)= ϕ(m1m2…mn)ϕ(mn+1)= ϕ(m1) ϕ(m2)… ϕ(mn)ϕ(mn+1).

Sia n>1 un numero naturale. Per il Teorema di Fattorizzazione Unica possiamo fattorizzare in modo unico n nel prodotto di numeri primi, e se raccogliamo sotto forma di potenza i fattori primi uguali, possiamo fattorizzare n in prodotto di potenze di primi distinti:

n = p1k1p2k2....prkr con pi primi distinti, ki interi >0 , tutti univocamente determinati.

Conoscendo la fattorizzazione di n, si può facilmente calcolare la funzione di Eulero ϕ(n).

Infatti si può notare che due potenze di primi distinti ph, qk sempre sono numeri coprimi: se per assurdo fosse d=mcd(ph,qk)>1, considerato un divisore primo p0 di d si avrebbe p0ph, p0qk, dunque (essendo p0 primo) p0p, p0q e infine p0=p=q, contraddizione.

Basta allora applicare il Teorema precedente e la formula per il calcolo della funzione di Eulero per le potenze di primi per ricavare:

ϕ(n) = ϕ(p1k1) (ϕ p2k2).... (ϕ prkr)= p1k1-1(p1-1)p2k2-1(p2-1)....prkr-1(pr -1)

La formula precedente, con semplici passaggi algebrici, si può trasformare nella seguente:

ϕ(n) = n(1-1/p1)(1-1/p2)…..(1-1/pr) .

Dunque un possibile algoritmo per il calcolo di ϕ(n) (dato in input l’intero n>1) è il seguente:

1) Si calcolano i fattori primi di n con un algoritmo di fattorizzazione 2)

Se x=L(n) la parte 2) dell’algoritmo ha ovviamente complessità polinomiale rispetto ad x: si può notare che si tratta di calcolare il prodotto di fattori pi , (pi-1) tutti ≤ n (quindi tutti di lunghezza ≤ x=L(n)), ed inoltre il numero dei fattori è k1+k2+….+kr< x (ciò deriva dall’osservazione che, essendo ogni pi >1 si ha n = p1k1p2k2....prkr≥2 2 ....2k1 k2 kr =2k1+k2....+kr) : in questa situazione, come sappiamo dalle considerazioni fatte sulla complessità delle operazioni aritmetiche, tale calcolo si può fare con un algoritmo di complessità polinomiale (rispetto ad x).

Per avere però la complessità dell’algoritmo “globale” che, dato in input un intero n>1, calcoli la sua funzione di Eulero, si dovrebbe sommare anche la complessità di un algoritmo che calcoli i fattori primi di n: attualmente però, come già detto, non esiste un algoritmo di fattorizzazione di complessità polinomiale, quindi la formula precedente non ci permette di trovare un algoritmo di complessità polinomiale per calcolare la funzione di Eulero di n.

Potrebbe naturalmente esistere un algoritmo di complessità polinomiale che, dato un naturale n>1 in input, calcoli la funzione di Eulero ϕ(n), senza calcolare i fattori primi di n: tuttavia a tutt’oggi non esiste un algoritmo di questo tipo (e i matematici dubitano che esista).

(5)

Anzi molti matematici sono convinti che sia vera la seguente congettura: esiste un algoritmo di fattorizzazione di complessità polinomiale ⇔ esiste un algoritmo di complessità polinomiale che calcola la funzione di Eulero (l’implicazione ⇒ è certamente vera per le considerazioni precedenti).

Ad avvalorare tale congettura, si può notare che essa è vera nel caso particolare in cui n=pq sia prodotto di 2 primi distinti p, q (caso che ritroveremo nel sistema crittografico RSA).

Infatti, se supponiamo che esista un algoritmo di complessità polinomiale che, dato in input n>1, calcola la funzione di Eulero ϕ(n) = (p-1)(q-1)= pq-(p+q)+1=n-(p+q)+1, è possibile calcolare, con complessità polinomiale, anche la somma p+q= n-ϕ(n)+1, da cui, impostando un classico sistema somma-prodotto è possibile ricavare i valori dei fattori p, q come soluzioni di un’equazione di secondo grado x2-(p+q)x+pq = 0 con coefficienti tutti di lunghezza ≤ x=L(n) e tali soluzioni si possono calcolare con un algoritmo di complessità polinomiale (come vedremo in seguito….).

Riferimenti

Documenti correlati

La funzione componi_importo stampa la quantità di ciascuna moneta necessaria per comporre un certo importo, utilizzando monete i cui valori disponibili sono

La funzione componi_importo stampa la quantità di ciascuna moneta necessaria per comporre un certo importo, utilizzando monete i cui valori disponibili sono

• Si presenti la costruzione dei numeri razionali a partire dai numeri interi (si scelga se fare una lezione o presentare il tutto in modo formale);2. • Si dimostri formalmente che

Questo esempio elementare mette in evidenza come due istanze di uguale dimen- sione dello stesso problema, possono provocare due comportamenti completamente diversi da parte di

Dato un file testo.txt composto da almeno N righe di testo non vuote, si scriva una funzione stringa_da_file() che crea una stringa di N caratteri composta dall’ultimo

Si scriva una funzione ordina() che crea un nuovo file chiamato num_org.dat che contenga gli stessi numeri del file numeri.dat ma ordinati in senso decrescente.. La

Sia dato un file città.dat contenente, in ogni riga, una stringa di lunghezza massima 36 caratteri che contiene il nome di una città e un valore intero che ne rappresenta il numero

Scrivere una funzione elimina(l) che riceve in ingresso la lista l e la modifica eliminando tutti gli elementi che hanno il campo informativo uguale a quello