Capitole Speciale de Informatica

Aplicatii ale Algoritmului lui Euclid

Cursul 3

Mircea Marin

Algoritmul euclidian extins are aplicatii numeroase ın calculul simbolic. Inacest capitol vom prezenta felul ın care acest algoritm este folosit pentru:

• aritmetica modulara, ın particular pentru calculul unui invers modular

• rezolvarea ecuatiilor liniare diofantice

• fractii continue; acest tip de fractii este important nu numai ın calcululsimbolic, ci si ın alte domenii precum: studiul calendarelor astronomice,si studiul sistemelor sonore de ınaltimi muzicale.

Reamintim ca ın cursul 2 a fost prezentat felul ın care algoritmul euclidian extinscalculeaza cel mai mare divizor comun si cofactorii euclidieni pentru o perechede 2 numere ıntregi sau pentru o pereche de polinoame. De exemplu:

• Pentru 2 numere ıntregi nenule m,n, ExtendedEuclid(m,n) calculeazaun triplet (d, s, t) de numere ıntregi astfel ıncat

– d = gcd(m,n)

– d = s ·m+ t · n.

– Pentru 2 polinoame nenule f, g ∈ K[x] (unde K poate fi orice camp,de exemplu Q, R, sau C), ExtendedEuclid(f, g) calculeaza untriplet (d, s, t) de polinoame din K[x] astfel ıncat

∗ d = gcd(m,n)

∗ d = s · f + t · g.

In ambele cazuri, s si t se numesc cofactorii euclidieni ai volorilor de intrare(numerele m si n, respectiv polinoamele f si g).

Am vazut ca algoritmul lui Euclid poate fi folosit pentru calculul cu numereıntregi m,n ∈ Z si pentru calculul cu polinoame f, g ∈ K[x]. Acest lucru esteposibil pentru ca Z si K[x] sunt domenii integrale R pentru care este definita ofunctie d : R → N ∪ {−∞} si o operatie de ımpartire a oricarui numar a la altnumar b 6= 0 care produce doua numere q si r astfel ıncat

a = q · b+ r si d(r) < d(b).

1

q se numeste catul ımpartirii lui a cu b, si se denoteaza quot(a, b).r se numeste restul ımpartirii lui a cu b, si se denoteaza rem(a, b).

In general, o multime R care satisface aceste conditii se numeste domeniueuclidian.

Algoritmul euclidian extins este remarcabil prin simplitatea sa. In pseudo-cod, acest algoritm poate fi descris astel:

Algoritm ExtendedEuclid(f,g)Intrare: f, g ∈ R unde R este un domeniu euclidianIesire: ` ∈ N si ri, si, ti ∈ R pentru 1 ≤ i ≤ `+ 1 si qi ∈ R pentru 1 ≤ i ≤ R,calculate ın felul urmatorbegin

r0 := f, s0 = 1, t0 = 0,r1 := g, s1 = 0, t1 = 1,

while r1 6= 0q := quot(r0, r1)r := r0 − q · r1s := s0 − q · s1r := r0 − q · r1, s := s0 − q · s1 t := t0 − q · t1,r0 := r1, s0 = s1, t0 := t1,r1 := r, s1 := s, t1 := t

endend si ın final produce r` = gcd(f, g) astfel ıncat r` = s` · f + t` · g.

Exemple 1 1. Pentru R = Z, f = 126 si g = 35, algoritmul calculeazasecventa urmatoare

i qi ri si ti0 126 1 01 3 35 0 12 1 21 1 −33 1 14 −1 44 2 7 2 −75 0 −5 18

si afla ca ` = 4, deci gcd(126, 35) = r4 = 7 = 2 · 126 + (−7) · 35.

2. Pentru R = Q[x], f = 18x3 − 42x2 + 30x − 6, g = −12x2 + 10x − 2algoritmul calculeaza valorile indicate ın tabelul de mai jos:

i qi ri si ti0 18x3 − 42x2 + 30x− 6 1 01 − 3

2x+ 94 −12x2 + 10x− 2 0 1

2 − 83x+ 4

392x−

32 1 3

2x−94

3 0 83x−

43 4x2 − 8x+ 4

si afla ca ` = 2, deci gcd(f, g) = r2 = 92x−

32 = 1 · f +

(32x−

94

)· g.

In restul acestui capitol vom prezenta aplicatii ale algoritmului lui Euclid.

2

1 Aplicatia 1: Aritmetica modulara

Verificarea corectitudinii programelor este extrem de importanta ın informatica.Se cunosc situatii grave cand algoritmi implementati ın hardware efectuau eroride operatii aritmetice, greu de detectat.

Studiul aritmeticii modulare are numeroase aplicatii practice. O aplicatieextrem de importanta este verificarea corectitudinii unui algoritm de ınmultirea numerelor mari. Presupunem ca:

• Avem acces la un algoritmul Prod(a, b) de ınmultire a numerelor a sib. Algoritmul nu ne apartine si nu putem verifica felul ın care a fostimplementat.

• Vrem sa verificam acuratetea rezultatului Prod(a, b) = a · b pentru nu-meroase valori mari ale lui a si b, de ex. cand a si b au fiecare mai multde 1000 cifre.

• Nu vrem sa ne pierdem timpul calculand a · b.

O solutie eleganta este un test modular:

• Se alege un numar prim p si se verifica daca a · b ≡ Prod(a, b) mod p. Peromaneste, spunem ca verificam ca “a · b este egal cu Prod(a, b) modulop.” Acest lucru ınseamna ca verificam daca a · b si Prod(a, b) producacelasi rest la ımpartirea cu p.

• Este important sa se observe ca acest test nu necesita calculul lui a · b,care este produsul a doua numere extrem de lungi. Pentru a calcula restullui a · b la ımpartirea cu p, este suficient sa calculam: a∗ = rem(a, p),b∗ = rem(b, p), si apoi c∗ = rem(a∗b∗, p). De exemplu, daca p are 63 cifre,atunci a∗ si b∗ au lungime ≤ 63 cifre, iar calculul lui a∗b∗ este mult mairapid decat calculul lui a · b.

• Testul modular este simplu si eficient. Este un test probabilist, deoareceeste posibil ca

a · b ≡ Prod(a, b) mod p dar a · b 6= Prod(a, b).

Numarul de erori nedetectate din cauza acestui fapt poate fi redus dra-matic daca se fac teste cu mai multe numere prime.

Pentru a aprecia avantajele testelor modulare, este important sa ıntelegemce este aritmetica modulara: care sunt operatii modulare, si cat de eficient potfi efectuate.

1.1 Aritmetica modulara

Aritmetica modulara este aritmetica cu resturi ale ımpartirii cu o cantitatem 6= 0 ıntr-un domeniu euclidian.

Daca 0 6= m ∈ R unde R este un domeniu euclidian (de exemplu, Z sauQ[x]), atunci definim multimea resturilor de ımpartire cu m astfel:

3

R/mR := {r ∈ R | r = rem(a,m) pentru un a ∈ R}.

• Daca m = 7 ∈ Z atunci Z/mZ = Z/6Z = {0, 1, 2, 3, 4, 5, 6}.

• Daca m = 6 ∈ Z atunci Z/mZ = Z/6Z = {0, 1, 2, 3, 4, 5}.

• In general, Z/mZ se prescurteaza scriind doar Zm.

• Daca m = x2 + 2x− 3 ∈ Q[x] atunci Q[x]/mQ[x] = {a x+ b | a, b ∈ Q}.

Este usor de observat ce putem face cu resturile ımpartirii cu m:

• Adunare modulara ⊕ : (R/mR)× (R/mR)→ (R/mR)

r1 ⊕ r2 := rem(r1 + r2,m).

• Scadere modulara : (R/mR)× (R/mR)→ (R/mR)

r1 r2 := rem(r1 − r2,m).

Deasemenea, putem defini

r := rem(−r,m)

si observam caa b = a⊕ ((b))a a = 0.

• Inmultire modulara � : (R/mR)× (R/mR)→ (R/mR)

r1 � r2 := rem(r1 · r2,m).

Observati ca, de obicei r1 ⊕ r2 6= r1 + r2, r1 r2 6= r1 − r2, si r1 � r2 6= r1 · r2.De exemplu, ın Z6 avem

• 3 + 3 = 6 6= 0 = 3⊕ 3.

• 1− 4 = −3 6= 3 = 1 4.

• 4 · 4 = 16 6= 4 = 4� 4.

Prin urmare, ın R/mR putem aduna, scadea, si calcula inversul unui elementın raport cu ⊕. Rezulta ca R/mR are proprietatile unui inel.

Ce putem spune despre ımpartire si inversare? In multimi care sunt corpuri(de ex., Q si C) orice element poate fi ımpartit cu un element nenul, si oriceelement nenul a are un invers a−1. In cazul nostru, vrem sa stim daca:

• Are sens sa ımpartim doua numere a, b ∈ R/mR cand m 6= 0? Daca da,atunci cum putem calcula rezultatul ımpartirii?

• Are sens sa definim a−1 pentru un element nenul a ∈ mR? Daca da, cumpoate fi calculat?

4

De exemplu, se observa ca pentru 5 ∈ Z6 are sens sa definim

• 35 = 3 deoarece 5 · 3 = rem(15, 6) = 3

• 5−1 = 5 deoarece 5 · 5 = rem(5 · 5, 6) = 1.

Pentru a ıntelege ce se petrece, definim mai ıntai urmatoarele notiuni ajutatoareıntr-un inel oarecare R:

• a este o unitate daca exista b ∈ R astfel ıncat a · b = 1.

• a, b ∈ R sunt elemente asociate, si scriem a ∼ b, daca exista o unitateu astfel ıncat a = b · u.

• In general scriem a | b si spunem ca a divide b daca exista c ∈ R astfelıncat a = b · c.

• a este un element prim daca nu este unitate si daca a | b · c atunci a | bsau a | c.

• a este ireductibil daca b | a implica b este unitate sau b ∼ a.

• a este un divizor al lui 0 daca a 6= 0 si a · b = 0 pentru un b 6= 0.

Exercitiu 1 1. Care sunt unitatile inelelor Z,Q, Q[x] si Z5?

2. Care sunt divisorii lui zero ın inelul Z6?

3. Sa se arate ca 1 ∼ 5 ın Z6.

Rezultatul urmator ne spune care sunt elementele inversabile ın R/mR:

Teorema 1 Daca R este un domeniu euclidian si a ∈ R, atunci a/mR esteinversabil daca si numai daca gcd(a,m) = 1. In acest caz, inversul modular allui a ın R/mR poate fi calculat cu algoritmul euclidian extins.

Demonstratia acestei teoreme este extrem de simpla. Daca gcd(a,m) = 1 atuncialgoritmul euclidian extins va calcula (d, s, t) unde d = gcd(a,m) = 1 astfel ıncat

d = s · a+ t ·m.

Rezulta ca 1 = rem(1,m) = rem(s · a + t ·m,m) = rem(s · a,m) = rem(s,m) �rem(t,m), adica rem(t,m) este inversul modular al lui a.

Exemple 2 1. Inversul elementului 12 ın Z29 se poate calcula astfel:ExtendedEuclid(12, 29) ne va indica ca gcd(12, 29) = 1 = 5·29+(−12)·12, deci 12−1 = rem(−12, 29) = 17 ın Z29.

2. Daca m = x3 − x− 2 ∈ Q[x] si a = x2, sa se arate ca a este inversabil ınQ[x]/mQ[x].

Raspuns. ExtendedEuclid(a,m) ne va indica ca gcd(a,m) = 1 =( 14x + 1

2 ) · m + (−14 x

2 − 12x + 1

4 ) · x2, de unde rezulta ca inversa lui x2

modulo x3 − x+ 2 este (−x2 − 2x+ 1)/4.

5

Teorema 1 ne mai spune un fapt important:

• Daca m este ireductibil atunci R/mR are toate elementele nenule inver-abile. Altfel spus, R/mR este un camp.

• Daca m este reductibil atunci R/mR este un inel cu divizori ai lui zero,deci nu poate fi camp.

Exemple 3 1. Este binecunoscut faptul ca un numar este ireductibil ın Zdaca si numai daca este prim. Prin urmare, toate multimile de resturi Zpsunt campuri atunci cand p este numar prim. Aceste campuri sunt finite,deoarece Zp are p elemente.

2. Putem construi campuri finite de polinoame, ın felul urmator:

• Incepem cu campul finit Zp si construim inelul de polinoame Zp[x].Zp[x] este infinit, deoarece putem avea polinoame de orice grad. Inpolinom din Zp[x] este de forma

an xn + an−1 x

n−1 + . . .+ a1 x+ a0

unde an, an−1, . . . , a0 ∈ Zp si an 6= 0. n se numeste gradul lui f .

• Alegem din Zp[x] un polinom ireductibil f de gradul n. (Observatie:este binecunoscut faptul ca pentru orice numar prim p si n ∈ N existaun astfel polinom ireductibil.)

• Din cele observate anterior, rezulta ca Zp[x]/fZp[x] este un camp.Elementele lui Zp[x]/fZp[x] sunt resturile posibile ale ımpartirii cuf , deci de forma

bn−1 xn−1 + bn−2 x

n−2 + . . .+ b1 x+ b0

unde bn−1, bn−2, . . . , b0 ∈ Zp. Observati ca exista doar un numat finitde astfel de polinoame!Intrebare: Cate elements are campul Zp[x]/fZp[x]?

Extensii algebrice ale unui camp

Se stie ca multimea numerelor complexe C este multimea numerelor de formaa+b·i unde i este numarul imaginar

√−1. Altfel spus, i2+1 = 0. Daca ın loc de

i folosim necunoscuta x atunci stim ca x2+1 = 0. Putem tine cont de acest faptdaca simplificam toate expresiile polinomiale E ın x calcland rem(E, x2 +1). Deexemplu, putem simplifica i3 + 2 i+ 1 = i+ 1.

Daca ınlocuim i cu x si calculam modulo x2 + 1, avemx3 + 2x+ 1 mod x2 + 1 = x+ 1, care este reprezentarea lui i+ 1.

Cum putem calculai+ 1

i− 1folosind aritmetica modulara ın R[x]/(x2+1)R[x]?

Avemx+ 1

x− 1= (x+ 1) · (x− 1)−1.

6

Algoritmul euclidian extins ne spune ca gcd(x2 + 1, x − 1) = 1 = 12 (x2 + 1) +

(− 12x−

12 )(x− 1) deci (x− 1)−1 = − 1

2x−12 mod (x2 + 1)

si prin urmare (x+ 1) · (x− 1)−1 = (− 12x−

12 )(x+ 1) = −x mod (x2 + 1).

Altfel spus,i+ 2

i− 1= −i.

Asadar, R[x]/(x2 + 1) coincide cu campul C obtinut prin extinderea lui Rcu radacina α =

√−1 a polinomului x2 + 1.

In general, daca f ∈ K[x] este un polinom ireductibil, atunci K[x]/f ·K[x]este un camp care coincide cu campul obtinut prin adaugarea radacinii α aecuatiei f(x) = 0 la campul f . Un astfel de camp se numeste extensie alge-brica a lui K si se noteaza cu K(α).

Un polinom f ∈ K[x] care are coeficientul celui mai semnificativ termen egalcu 1 se numeste polinom monic.

Un numar α se numeste algebric peste un camp K daca este radacina aunui polinom nenul f ∈ K[x], adica f(α) = 0. Un numar care nu este algebricpeste K se numeste transcendental peste K.

De exemplu, numarul i este algebric peste R deoarece este radacina polino-mului x2 + 1 ∈ R[x].

Fie α un numar algebric. Atunci multimea Mα a tuturor polinoamelor areau α ca radacina este nevida, si putem alege din Mα un polinom f care aregradul minim posibil:

f = anxn + an−1 x

n−1 + . . .+ a1 x+ a0

cu deg(f) = n > 0. Se observa ca polinomul

g = a−1n f = xn +

an−1

anxn−1 + . . .+

a1anx+

a0an

este monic, cu gradul cel mai mic posibil pentru a avea radacina α.

Exercitiu 2 Sa se demonstreze ca, daca α este un numar algebric peste K,atunci exista un singur polinom monic ireductibil care are radacina α. Acestpolinom se numest e polinom caracteristic al lui α ın K[x].

Exemplu

Sa presupunem ca extindem campul Q cu elementul α =√

3−√

2. Cum arata e-lementele multimii Q(α), ın care putem efectua orice adunari, ınmultiri, scaderi,si ımpartiri cu elemente nenule? In particular, cum putem reprezenta numarul

3α5 − 2

α4 + α3 + α2 − 7?

Raspuns:

7

• α este un numar format prin aplicarea de radicali la numere rationale ⇒putem gasi un polinom ireductibil a carui radacina este α. De exemplu:

α =√

3−√

2⇒ α2 = 3 + 2− 2√

6

⇒ α2 − 5 = −2√

6⇒ α4 − 10α2 + 25 = 24

⇒ α4 − 10α2 + 1 = 0

Pentru moment, acceptam faptul ca polinomul f = x4 + x2 + 1 ∈ Q[x]este ireductibil. Vom prezenta ın ultima mai tarziu un criteriu de verificarea faptului ca un polinom f ∈ Q[x] este ireductibil.

• α este radacina a polinomului ireductibil f ⇒ Q(α) coincide cu campulQ[x]/f ·Q[x]. Prin urmare, toate elementele lui Q(α) sunt de forma

b3 α3 + b2 α

2 + b1 α+ b0

unde b3, b2, b1, b0 ∈ Q. In particular, avem ca

3α5 − 2

α4 + α3 + α2 − 7= b3 α

3 + b2 α2 + b1 α+ b0

Ramane doar de calculat valorile numerelor b3, b2, b1, b0 ∈ Q. Algoritmuleuclidian extins poate fi folosit pentru a efectua toate aceste calcule:

rem(3α5 − 2, α4 + α2 + 1) = −3α3 − 3α− 2

rem(α4 + α3 + α2 − 7, α4 + α2 + 1) = α3 − 8

⇒ 3α5 − 2

α4 + α3 + α2 − 7=−3α3 − 3α− 2

α3 − 8

ExtendedEuclid(α3 − 8, α4 + α2 + 1) ne indica faptul ca

gcd(α3 − 8, α4 + α2 + 1) = 1 =(−α

3

63 −863

)· (α3 − 8) +

(α2

63 −163

)· f(α),

deci(α3 − 8

)−1= −α

3

63− 8

63mod α4 + α2 + 1 si

−3α3 − 3α− 2

α3 − 8= (−3α3 − 3α− 2)�

(−α3

63− 8

63

)=

26α3

63− α2

21+

8α

21+

16

63.

Compexitatea operatiilor modulare

Fie K un camp si f ∈ K[x] un polinom de gradul n. Dorim sa estimam com-plexitatea operatiilor de adunare (⊕), ınmultire (�) si ımpartire cu un elementinversabil, cand se presupune ca toate operatiile elementare din K au timpconstant de executie O(1).

Se poate demonstra ca:

8

• Adunarea modulo f necesita cel mult O(n) operatii elementare ın F .

• Inmultirea modulo f necesita cel mult 4n2 +O(n) operatii elementare ınF .

• Inversarea unui element inversabil modulo f necesita cel mult 6n2 +O(n)operatii elementare ın F .

2 Aplicatia 2: Metoda patratelor repetate

Aritmetica modulara joaca un rol important ın calculul eficient al unei valori an

cand a este un element al unui inel (de exemplu Q, R, C, K[x1, . . . , xm], etc.)Cum se poate evita efectuarea de n− 1 ınmultiri succesive?

Exemple:

• a64 se poate calcula cu 6 ınmultiri ın loc de 63, daca se observa ca a64 =(((((a2)2)2)2)2)2

• In general, daca n are reprezentarea binara bkbk−1 . . . b1b0 cu bk = 1 sibi ∈ {0, 1} pentru 0 ≤ i < k, atunci putem defini algoritmul patratelorrepetate:

Algoritm PatrateRepetate(a, n)Intrare: a ∈ R, n ∈ N− {0}Iesire: an ∈ Rbegin

Calculeaza reprezentarea binara bkbk−1 . . . b1b0 a lui nr := afor i := k − 1 downto 0 do

if bi = 0 then r := r2 · a else r := r2

return rend

Compexitatea metodei patratelor repetate

• Numar de ridicari la patrat = blog2 nc

• Numar de ınmultiri ın R = w(n)− 1 unde w(n) este numarul de biti 1 ınreprezentarea binara a lui n. w(n) se numeste greutatea Hamming alui n. Evident ca w(n) ≤ blog2 nc.

⇒ numar total de operatii = O(blog2 nc).

9

3 Aplicatia 3: Calculul inversului modular cumetoda lui Fermat

Reamintim formula binomiala bine cunoscuta din calculul algebric:

(a+ b)p =

p∑i=0

(p

i

)ap−1bi = ap + p ap−1b+

p(p− 1)

2a2bp−1 + . . .+ p a bp−1 + bp

In cazul ın care calculele se fac ın campul Zp, avem p = 0 mod p. Deoarece papare ca factor ın toti coeficientii lui aibp−i din formula de mai sus, cu exceptiatermenilor ap si bp, tragem concluzia ca ın Zp are loc egalitatea:

(a+ b)p = ap + bp.

Aceasta formula poate fi folosita pentru a da o demonstratie foarte simpla uneiteoreme faimoase din teoria numerelor:

Teorema 2 (Mica teorema a lui Fermat) Daca p ∈ N este numar prim sia ∈ Z atunci ap ≡ a mod p si, daca p - a atunci ap−1 ≡ 1 mod p.

Demonstratie. Prin inductie dupa a ∈ {0, 1, . . . , p − 1}. Daca a = 0 atunciap = 0p = 0 = a, deci teorema are loc pentru a = 0.

Presupunem ca teorema are loc pentru a ∈ {0, . . . , a − 1}. In acest caz,putem scrie ap = ((a − 1) + 1)p = (a − 1)p + 1p. Conform ipotezei inductive,avem (a− 1)p ≡ a− 1 mod p. Rezulta ca ap ≡ a− 1 + 1 ≡ a mod p. �

Acest rezultat ne indica faptul ca inversul unui element nenul a ın Zp esteap−2. Prin urmare, putem folosi metoda patratelor repetate pentru a calculaa−1 ın Zp ın O(blog2 nc) pasi.

4 Rezolvarea ecuatiilor liniare diofantice

O ecuatie liniara diofantica este o ecuatie liniara de forma

s · f + t · g = a (1)

unde s, t, a ∈ Z sunt valori constante date, iar f si g sunt necunoscute pentrucare se cauta solutii ıntregi care satisfac relatia (1).

Daca ın loc de solutii ıntregi se cauta solutii reale, atunci se cunoaste faptulca multimea solutiilor ecuatiei (1) este situata pe o linie dreapta ın planul R2,si ca poate fi reprezentata ca suma v +U dintre o solutie particulara a ecuatiei(1) si multimea U a solutiilor ecuatiei omogene

s · f + t · g = 0.

Un fapt remarcabil este ca acest rezultat ramane adevarat cand ne restrangematentia doar la solutii ıntregi. Mai mult, putem folosi algoritmul euclidian extinsca sa gasim toate solutiile ecuatiei (1).

Problema ramane la fel de interesanta si poate fi rezolvata la fel daca segeneralizeaza ın felul urmator:

10

• f, g si a sunt elementele unui domeniu integral R,

• dorim sa gasim toate valorile posibile din R pentru s si t astfel ıncats · f + t · g = a.

Se cunoaste urmatorul rezultat:

Teorema 3 Fie R un domeniu euclidian, a, f, g ∈ R si h = gcd(f, g).

1. Ecuatia (1) are solutii daca si numai daca h | a.

2. Daca h 6= 0 si (s∗, t∗) ∈ R2 este solutie a ecuatiei (1), atunci multimeatuturor solutiilor este (s∗, t∗) + U unde

U =

{(g

h· r, f

h· r)| r ∈ R

}.

3. Daca

• R este un camp,

• ecuatia (1) este rezolvabila, si

• deg(f) + deg(g)− deg(h) > deg(a)

atunci exista s solutie unica (s, t) ∈ R2 ecuatiei (1) astfel ıncat deg(s) <deg(g)− deg(h) si deg(t) < deg(f)− deg(h).

Bibliografie

Capitolul 4 din

• Joachim von zur Gathen, Jurgen Gerhard. Modern Computer Algebra.Second Edition. Cambridge University Press, 2003.

11