xzmmmxbm  (mod...)(mod) xx  1(mod3)2(mod5)

Teoria dei numeri e Crittografia: lezione del 20 aprile 2011 Esempio.

Risolviamo il sistema formato dalle prime 2 congruenze del problema del manoscritto cinese:

1(mod 3) 2(mod 5) x

x

 

  

Le soluzioni della prima congruenza sono della forma x=1+3y, con y intero, e imponendo che siano soluzioni anche della seconda si ottiene la congruenza di primo grado in y:

3y1 (mod 5)

Una soluzione è y=ts, dove t si ottiene dividendo il termine noto 1 per il mcd(3,5)=1(quindi t=1), ed s è il coefficiente di 3 nella rappresentazione di 1=mcd(3,5) come combinazione lineare di 3 e 5:

quindi da 1=32+5(-1) segue s=2. Si ha y=2, e una soluzione del sistema è allora x=1+3y=7: tutte le soluzioni del sistema sono i numeri della classe di congruenza [7] 15 rappresentata da 7 modulo 15, dunque tutti gli interi della forma 7+15k, con k intero relativo (per esempio i numeri -8, 22, 37 etc…).

Nel caso generale di n congruenze si ottiene un risultato analogo a quello del caso n=2:

Teorema (Teorema Cinese del Resto nel caso generale di n congruenze).

Nel sistema (*), con n>1 qualunque, se i moduli m 1 sono a due a due coprimi esiste una soluzione intera x=x 0 del sistema e le soluzioni del sistema sono tutti e soli gli interi x 1 tali che x 1 x (mod m 1 m 2 …m n ) (quindi gli elementi della classe di congruenza   x 0 m m

... m

rappresentata da x 0 modulo m 1 m 2 …m n ).

Dimostrazione:

Per induzione (I ^a forma) su n, con base n=2.

Per n=2 la tesi segue dal Teorema precedente.

Supponiamo il Teorema vero per n e dimostriamolo per n+1.

Dato il sistema di n+1 congruenze:

1 1

2 2

1 1

(mod ) (mod ) ...

...

(mod )

n n

x b m

x b m

x b _ m _

 

  

 

 



Per induzione esiste una soluzione intera z del sistema formato dalle prime n congruenze, e inoltre tutte e sole le soluzioni di tale sistema sono z (mod m 1 m 2 …m n ). Dunque il sistema di n+1 congruenze dato equivale al sistema di 2 congruenze:

1 2

1 1

(mod ... )

(mod )

n

n n

x z m m m

x b _ m _

 

  

Notiamo che i moduli delle 2 congruenze sono coprimi: se per assurdo d=mcd(m 1 m 2 …m n ,m n+1 )>1,

considerato un divisore primo p di d sarebbe p divisore del prodotto m 1 m 2 …m n (quindi p divisore di

qualche m i con i=1,2,…,n) e di m n+1 , contro l’ipotesi che m i ,m n+1 sono coprimi.

Per il Teorema precedente (il caso di 2 congruenze) si ha la tesi per n+1: il sistema ha soluzione x 0 e le soluzioni sono tutti e soli gli interi x 0 (mod m 1 m 2 …m n+1 ).

Fissata una soluzione x=x 0 del sistema (*), poiché tutte le soluzioni del sistema sono gli elementi della classe di congruenza modulo m 1 m 2 …m n rappresentata da x 0 , la riduzione modulo m 1 m 2 …m n di x 0 è anch’essa una soluzione ed è l’unica con valore compreso fra 0,1,…, m 1 m 2 …m n -1: tale soluzione è detta soluzione canonica del sistema (ovviamente essa è anche la minima soluzione 0 del sistema)

Esempio.

Risolviamo il sistema formato dalle 3 congruenze del problema del manoscritto cinese:

1(mod 3) 2(mod 5) 3(mod 7) x

x x

 

  

  

Abbiamo già risolto il sistema formato dalle prime 2 congruenze, le cui soluzioni sono 7 (mod 15).

Il sistema dato equivale allora al sistema di 2 congruenze:

7 (mod15) 3(mod 7) x

x

 

  

Le soluzioni della prima congruenza sono della forma x=7+15y con y intero, e imponendo che siano soluzioni della seconda si ottiene la congruenza in y:

15y -4 (mod 7).

Sostituendo -4 con la sua riduzione modulo 7, si ottiene la congruenza equivalente:

15y 3 (mod 7)

una cui soluzione è y=rs , dove r=3/mcd(15,7)= 3, s è il coefficiente di 15 nella rappresentazione di 1=mcd(15,7) come combinazione lineare di 15, 7 (si ha 1=151+7(-2), quindi s=1), e si ha y=3.

Una soluzione del sistema iniziale è allora x=7+153= 52.

La soluzione canonica del sistema è la riduzione 52mod(357)=52mod105=52 (è l’unica compresa fra 0,1,…,104). Quindi x=52 è la soluzione (minima fra quelle positive) del problema del manoscritto cinese.

Ragionando come nel caso della singola congruenza di primo grado, si verifica che nel sistema di n congruenze (supponendo i termini noti b i <m i quindi di lunghezza L(m)=x dove m è il più grande dei moduli m i ) si può trovare una soluzione con un algoritmo di complessità O(x ³ ) (almeno nel caso in cui il numero n di congruenze non dipende da m, perché se n=f(m) è funzione di m è ovvio che la complessità dipende da O(f)).

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 1 A 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 0 A 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 Z m

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

[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 Z m è gruppo commutativo (il neutro è [0], se 0 a <m l’opposto di [a] è [0] se a=0, mentre è [m-a] se a>0, perché [a]+[m-a]=[m]=[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]Z m 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 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 Z m .

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 Z m : sappiamo che la somma aritmetica a+b dei numeri naturali a,b ha

complessità 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à  O((x+1) ² +x)=O(x ² ).

Complessità del prodotto in Z m : sappiamo che il prodotto aritmetico ab dei numeri naturali a,b ha complessità O(x ² ) (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à  O((2x) ² +x ² )=O(x ² ).

Complessità del calcolo dell’opposto in Z m : dato a in Z m (con 0 a<m) per calcolare l’opposto rispetto alla somma (escludendo il caso banale a=0) si deve effettuare la sottrazione m-a, con complessità lineare O(x) (dove x=L(m)).

Per calcolare la complessità del calcolo dell’inverso in Z m , notiamo che non tutti gli elementi del monoide Z m sono invertibili rispetto al prodotto: per esempio [0] certamente non lo è, in quanto [0]

[x]=[0] per ogni [x] in Z m .

Per quanto riguarda le classi non nulle sussiste il seguente risultato:

Teorema.

Una classe [a]Z m , 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 Z m è [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 Z m , 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 Z m (se a,m sono coprimi).

Possiamo utilizzare l’algoritmo Euclideo esteso applicato ai numeri a, m : dopo avere eseguito n divisioni successive (per verificare che 1=mcd(m,a)), si costruiscono le successioni di interi non negativi s i ,t i con i=0,1,….,n+1, e si ha 1=m(-1) ⁿ s n +a(-1) ⁿ⁺¹ t n . Per quanto osservato prima, la classe di congruenza [(-1) ⁿ⁺¹ t n ] è l’inverso della classe [a] : dobbiamo solo riportare il rappresentante della classe nel “range” canonico dei numeri compresi fra 0 ed m.

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 particolare 0 t n  m. Notiamo anche che 0< t n < m (nei casi t n =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) ⁿ⁺¹ t n ])= [t n ] con 0< t n < m, e dunque (nella rappresentazione digitale) l’inverso di a è t n

- se il numero n delle divisioni effettuate è pari, allora [(-1) ⁿ⁺¹ t n ])= [-t n ]=[m-t n ] con 0<m - t n < m, e dunque (nella rappresentazione digitale) l’inverso di a è m - t n .

In ogni caso per calcolare l’inverso di a, si è eseguito l’algoritmo Euclideo esteso (di complessità

O(x ³ )) e (al più) la sottrazione m - t n (di complessità lineare O(x)).

In totale l’inverso di aZ m (se esiste) si può calcolare con un algoritmo di complessità O(x ³ ).

La funzione di Eulero.

Abbiamo dimostrato che, fissato il modulo m>1, le classi invertibili di Z m (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 Z m * degli elementi

invertibili del monoide Z m (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=p ^k 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p ^k si ha d=p ^h 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,p ^k ), si ha pp ^k , pa, dunque pd e si conclude che d>1 .

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

(p ^k )=p ^k -p ^k-1 =p ^k-1 (p-1)

In particolare se m=p primo, si ha:

(p)=p-1.