Teoria dei numeri e Crittografia: lezione del 2 novembre 2011 Congruenze aritmetiche.

Teoria dei numeri e Crittografia: lezione del 2 novembre 2011 Congruenze aritmetiche.

Ricordiamo la teoria delle congruenze aritmetiche.

La nozione di divisore (e simmetricamente quella di multiplo) si estende facilmente dall’insieme N dei numeri naturali all’insieme Z dei numeri interi relativi: dati gli interi relativi a,bZ si dice che a è divisore di b (o che b è multiplo di a) e si scrive ab, se esiste un intero relativo cZ tale che ac=b.

Fissato un intero relativo m (detto modulo), e dati i numeri interi relativi a,b, diremo che a è congruo b modulo m (e scriveremo ab (mod m)) se m(a-b).

In questo modo definiamo nell’insieme Z degli interi relativi una relazione, detta appunto congruenza modulo m, che è una relazione di equivalenza (come si dimostra facilmente).

Poiché è facile verificare che la congruenza modulo m coincide con la congruenza modulo –m, possiamo limitarci a studiare il caso di m0.

Poiché inoltre sono banali i casi m=0 (la congruenza modulo 0 non è altro che la relazione di eguaglianza) ed m=1 (nella congruenza modulo 1 tutti gli interi sono congrui fra loro) ci limiteremo a studiare il caso m>1.

Per ogni aZ si può costruire la classe di equivalenza rappresentata da a (detta classe di congruenza modulo m rappresentata da a):

[a] m = { xZ / xa (mod m) } = { xZ / x-a=km, con kZ } = { xZ / x=a+km, con kZ } (se non vi è possibilità di equivoco sul modulo m, useremo semplicemente il simbolo [a])

Per la teoria generale delle relazioni di equivalenza, dati a,bZ si ha [a]=[b] ab (mod m), e inoltre le classi di congruenza modulo m formano una partizione dell’insieme Z .

Teorema.

Fissato il modulo m>1, le classi di congruenza modulo m distinte sono tutte e sole le seguenti:

[0], [1], ……, [m-1] (*) Dimostrazione:

Le classi (*) sono distinte: se per assurdo fosse [a]=[b] con 0b<a<n, si avrebbe ab (mod m), dunque 0<a-b<m sarebbe un multiplo di m (contraddizione).

Per ogni aZ la classe di congruenza [a] coincide con una delle classi (*): infatti se a>0 allora, dividendo a per m con quoziente q e resto r si ha a=mq+r , a-r=mq, ar (mod m), [a]=[r], con r compreso fra i valori 0,1,…,m-1; se invece a<0 allora, dividendo (-a) per m con quoziente q e resto r si ha -a=mq+r , a-(m-r)=m(-q-1), am-r (mod m), [a]=[m-r], con m-r compreso fra 1,…,m-1 (se r>0) oppure (se r=0) con [a]=[m]=[0].

Poiché 0,1,…,m-1 sono i possibili resti delle divisioni per m, le classi di congruenza modulo m sono anche dette classi resto modulo m, e il loro insieme è indicato con Z m : per il Teorema precedente si ha Z m = { [0], [1], ……, [m-1] }, e la cardinalità di Z m è uguale al modulo m.

Nella dimostrazione del Teorema, per ogni intero relativo aZ si è costruito un (unico) intero t compreso fra i valori 0,1,…,m-1 tale che [a]=[t] (o equivalentemente tale che at (mod m)): tale t è detto riduzione modulo m dell’intero a ed è indicato con amodm.

Se in particolare a è un numero naturale, un algoritmo per il calcolo della sua riduzione modulo m è

indicato nella dimostrazione del Teorema: basta dividere a per m e considerare il resto r=amodm

(algoritmo, come sappiamo, di complessità quadratica).

Compatibilità della congruenza con somma e prodotto di interi.

Fissato il modulo intero m>1, e comunque dati gli interi relativi a,b,c,d , da:

ab (mod m), cd (mod m) seguono sempre:

a+cb+d (mod m) (compatibilità della congruenza rispetto alla somma) acbd (mod m) (compatibilità della congruenza rispetto al prodotto)

Infatti da m(a-b), m(c-d) si ha che esistono interi relativi h,k tali che a-b=hm, c-d=km da cui:

(a+c)-(b+d)=(h-k)m ac-bd=a(c-d)+d(a-b)=(ak+dh)m e si hanno le tesi m(a+c)-(b+d), mac-bd.

In particolare, comunque fissato un intero relativo y , da ab (mod m) seguono sempre:

a+yb+y (mod m) ayby (mod m)

(basta ricordare che per la proprietà riflessiva si ha yy (mod m)) Congruenze di primo grado ad una incognita.

Fissato il modulo m>1 e i numeri interi relativi a,b, poniamoci il problema di trovare (se esistono) tutti e soli gli interi relativi x tali che axb (mod m) . Diremo anche che tali valori x sono le soluzioni della congruenza axb (mod m) di primo grado nell’incognita x.

Sostituendo eventualmente a con amodm (la sua riduzione modulo m) otteniamo una congruenza equivalente (per la compatibilità della congruenza rispetto alla somma e al prodotto), dunque possiamo ricondurci sempre al caso in cui a 0 (ed anche a<m). Per evitare casi banali supporremo anche a>0 (se a=0 ovviamente la congruenza ha per soluzione ogni intero relativo se b0 (mod m), o in caso contrario non ha soluzioni).

Vediamo quando una soluzione della congruenza di primo grado esiste:

Teorema.

Fissato il modulo m>1 e i numeri interi relativi a,b, con a>0, e posto d=mcd(a,m):

esiste una soluzione x della congruenza axb (mod m)  d é divisore di b.

Dimostrazione:

(): Se axb (mod m), si ha ax-b=km, con kZ, da cui, essendo da, dm, ovviamente db.

(): Se db, posto dt=b, con tZ, e posto d=mcd(a,m)=az+mw, con z,wZ, si ottiene b=dt=azt+mwt, da cui aztb (mod m), e basta porre x=zt per ottenere una soluzione della congruenza.

Osservazione. Dal punto di vista algoritmico, per verificare se esiste una soluzione della congruenza axb (mod m) basta usare l’algoritmo Euclideo delle divisioni successive per calcolare d=mcd(a,m), e poi eseguire una divisione per verificare se db (complessità totale di ordine cubico).

La dimostrazione precedente fornisce anche un algoritmo per il calcolo di una soluzione x (se essa esiste cioè se db): basta moltiplicare t (ottenuto dividendo b per d) per z (coefficiente di a nella espressione del mcd(a,m) come combinazione lineare di a,m, calcolato con l’algoritmo Euclideo esteso): anche la complessità dell’algoritmo per il calcolo di una soluzione della congruenza è dunque di ordine cubico.

La soluzione (se esiste) della congruenza axb (mod m) non è unica, ma è possibile determinare

tutte le soluzioni, conoscendone una:

Teorema.

Fissato il modulo m>1 e i numeri interi relativi a,b, con a>0, e posto d=mcd(a,m):

se esiste una soluzione x 0 della congruenza axb (mod m) , tutte e sole le soluzioni sono i numeri interi relativi x 1 tali che x 1 x 0 (mod m/d) (ossia i numeri della classe di congruenza [x 0 ] m/d

rappresentata da x 0 modulo m/d).

Dimostrazione:

Sia x 1 una soluzione della congruenza.

Allora ax 1 b (mod m), ax 0 b (mod m), da cui per transitività ax 1 ax 0 (mod m), ax 1 -ax 0 =mk con k intero relativo, e dunque (a/d)(x 1 -x 0 )=(m/d)k.

Ma per una proprietà già dimostrata, i numeri a/d, m/d sono coprimi (essendo d=mcd(a,m)). Per una proprietà dei numeri coprimi essendo (m/d)(a/d)(x 1 -x 0 ) si ha (m/d)(x 1 -x 0 ) ottenendo infine la tesi x 1 x 0 (mod m/d).

Viceversa sia x 1 un intero relativo tale che x 1 x 0 (mod m/d).

Allora x 1 -x 0 =km/d, con k intero relativo, ax 1 -ax 0 =k(a/d)m, ax 1 ax 0 (mod m).

Ma per ipotesi ax 0 b (mod m), e per transitività anche ax 1 b (mod m), dunque anche x 1 è soluzione della congruenza.

Dai risultati precedenti segue che, fissato il modulo m>1 e i numeri interi relativi a,b, con a>0, posto d=mcd(a,m), e fissata una soluzione x=x 0 della congruenza axb (mod m), poiché tutte le soluzioni della stessa congruenza sono gli elementi della classe di congruenza modulo m/d rappresentata da x 0 , la riduzione modulo m/d di x 0 è anch’essa una soluzione ed è l’unica con valore compreso fra 0,1,…,(m/d)-1: tale soluzione è detta soluzione canonica della congruenza.

Esempio:

Risolviamo la congruenza 36x10 (mod 14).

Con l’algoritmo Euclideo, operando n=4 divisioni, otteniamo che d=mcd(36,14)=2, che è divisore di b=14.

Per calcolare i coefficienti interi z, w tali che 2=36z+14w, si costruiscono le successioni s i , t i (con i=0,1,2,3,4,5) di cui si è parlato nell’Algoritmo Euclideo esteso, e si trovano alla fine i valori:

z=s 4 =2, w= -t 4 = -5.

Una soluzione x della congruenza è data allora da x=tz=10 (dove t=b/d=5).

Tutte le soluzioni sono i numeri della forma 10+k(m/d)=10+7k, con k intero relativo (quindi gli elementi della classe di congruenza rappresentata da 10 modulo m/d=7) e la soluzione canonica è la riduzione 10mod7=3 (l’unica compresa fra 0,1,2,…,6).

Teorema Cinese del Resto.

In un manoscritto cinese del III° sec. a.C. si trova il seguente problema: trovare un intero positivo x che diviso per 3 dia resto 1, diviso per 5 dia resto 2, diviso per 7 dia resto 3.

Nel linguaggio delle congruenze si tratta di trovare un intero positivo che sia soluzione intera del seguente sistema di congruenze di primo grado nell’incognita x:

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

x x

 

  

  

Studieremo dunque i sistemi di congruenze di primo grado nell’incognita x in cui il coefficiente

della x sia = 1, ossia i sistemi di n congruenze della forma:

1 1

2 2

(mod ) (mod ) ...

...

(mod )

n n

x b m

x b m

x b m

 

  

 

 



(*)

(dove sono fissati i moduli m i >1 ed i termini noti b i sono supposti non negativi, eventualmente sostituendo ognuno di essi con la sua riduzione modulo m i ).

Studiamo prima il caso di 2 congruenze:

Teorema (Teorema Cinese del Resto nel caso di 2 congruenze).

Nel sistema (*), con n=2, se i moduli m 1 ,m 2 sono 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 0 (mod m 1 m 2 ) (quindi gli elementi della classe di congruenza   ^x _{0 m m}

rappresentata da x 0 modulo m 1 m 2 ).

Dimostrazione:

Le soluzioni della prima congruenza del sistema sono tutti gli interi della classe di congruenza rapprresentata da b 1 modulo m 1 , dunque gli interi della forma x=b 1 +m 1 y, dove y varia fra gli interi relativi. Imponiamo la condizione che uno di tali interi x sia soluzione anche della seconda congruenza, ottenendo la seguente congruenza di primo grado nell’incognita y:

m 1 y(b 2 -b 1 ) (mod m 2 )

Sappiamo che tale congruenza ha qualche soluzione y=y 0 perché mcd(m 1 ,m 2 )=1 è ovviamente divisore della differenza (b 2 -b 1 ). Ponendo x 0 =b 1 +m 1 y 0 otterremo una soluzione del sistema.

E’ facile verificare che ogni numero intero x 1 x 0 (mod m 1 m 2 ) è anche soluzione del sistema, in quanto x 1 x 0 b 1 (mod m 1 ) e x 1 x 0 b 2 (mod m 2 ).

Viceversa se x 1 è soluzione intera del sistema, allora x 1 x 0 b 1 (mod m 1 ) e x 1 x 0 b 2 (mod m 2 ), dunque m 1 ,m 2 sono divisori di (x 1 -x 0 ), e per una proprietà dei numeri coprimi anche il prodotto m 1 m 2

è divisore di (x 1 -x 0 ), ossia x 1 x 0 (mod m 1 m 2 ).

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