Prošireni Euklidov algoritam

Prošireni Euklidov algoritam, pored pronalaženja najvećeg zajedničkog djelioca cijelih brojeva a i b, što radi obični Euklidov algoritam, takođe nalazi cijele brojeve h i u (od kojih je uglavnom jedan negativan) koji zadovoljavaju Bezuov stav:

$ax+by=nzd(a,b)$

Prošireni Euklidov algoritam je posebno koristan kada su a i b uzajamno prosti, pošto je h modularni multiplikativni inverz od a po modulu b, a y je modularni multiplikativni inverz od b po modulu a. Ovo ima značaj u izračunavanju ključa u RSA algoritmu za šifrovanje javnog ključa; nalaženje celobrojnog eksponenta za dešifrovanje d koji je modularni multiplikativni inverz izabranog eksponenta e po modulu φ(n), gde su e i φ(n)uzajamno prosti.

Neformalna formulacija algoritma

Djeljenik	Djelilac	Količnik	Ostatak
120	23	5	5
23	5	4	3
5	3	1	2
3	2	1	1
2	1	2	0

Da bismo ilustrovali proširenje Euklidovog algoritma, razmotrimo izračunavanje nzd(120, 23), koji je prikazan u tabeli. Primijetimo da je količnik u svakom dijeljenju zabilježen kao i ostatak.

U ovom slučaju, djelilac u posljednjem redu (koji je jednak 1) nam govori da je nzd 1; to jest, 120 i 23 su uzajamno prosti (takođe se nazivaju i relativno prosti). Zbog jednostavnosti, izabrani primjeri su par uzajamno prostih; ali u opštijem slučaju nzd-a koji nije 1, ovo slično funkcioniše.

Postoje dva metoda u nastavku, od kojih oba koriste algoritam cjelobrojnog dijeljenja kao podpostupak, od kojih će svaki biti zasebno diskutovan.

Iterativna metoda

Ovaj metod računa izraze oblika 

$r_{i}=ax_{i}+by_{i}$ za ostatak u svakom koraku i  Euklidovog algoritma. Svaki uzastopni broj

$r_i$ može biti zapisan kao ostatak pri dijeljenju prethodna dva takva broja, čiji ostatak može biti izražen koristeći cio količnik

$q_i$ tog dijeljenja prema formuli: 

$r_{i}=r_{i-2}+q_{i}r_{i-1}$

Kada se zamijene vrijednosti, ovo daje:

$r_{i}=(ax_{i-2}+by_{i-2})-q_{i}(ax_{i-1}+by_{i-1}),\,$

što može da se zapiše kao

$r_{i}=a(x_{i-2}-q_{i}x_{i-1})+b(y_{i-2}-q_{i}y_{i-1}).\,$

Prve dvije vrijednosti su polazni argumenti za algoritam:

$r_{1}=a=a\times 1+b\times 0\,$

$r_{2}=b=a\times 0+b\times 1.\,$

Dakle, početni koeficijenti su x₁ = 1, y₁ = 0, x₂ = 0, i y₂ = 1, a drugi su dati kao

$x_{i}=x_{i-2}-q_{i}x_{i-1},\,$

$y_{i}=y_{i-2}-q_{i}y_{i-1}.\,$

Izraz za poslednji ne-nula ostatak daje željeni rezultat, pošto ovaj metod računa svaki ostatak u odnosu na a i b, kao što je i željeno.

Primjer: izračunati NZD od 120 i 23

Računanje teče prema narednoj tabeli:

Korak	Količnik	Ostatak	Zamjena	Kombinovani uslovi
1		120		120 = 120 × 1 + 23 × 0
2		23		23 = 120 × 0 + 23 × 1
3	5	5 = 120 − 23 × 5	5 = (120 × 1 + 23 × 0) − (120 × 0 + 23 × 1) × 5	5 = 120 × 1 + 23 × −5
4	4	3 = 23 − 5 × 4	3 = (120 × 0 + 23 × 1) − (120 × 1 + 23 × −5) × 4	3 = 120 × −4 + 23 × 21
5	1	2 = 5 − 3 × 1	2 = (120 × 1 + 23 × −5) − (120 × −4 + 23 × 21) × 1	2 = 120 × 5 + 23 × −26
6	1	1 = 3 − 2 × 1	1 = (120 × −4 + 23 × 21) − (120 × 5 + 23 × −26) × 1	1 = 120 × −9 + 23 × 47
7	2	0	Kraj algoritma

U poslednjem redu stoji 1 = 120 × −9 + 23 × 47, što je traženo rešenje: x = −9 i y = 47.

Pošto je NZD 1, ovo takođe znači da 47 daje multiplikativni inverz od 23 po modulu 120, a takođe po modulu 23, -9 (ili 14, koji predstavljaju isti element) daje multiplikativni inverz od 120 (ili, ekvivalentno, od 5).

47 × 23 ≡ 1 (mod 120) i takođe −9 × 120 ≡14 × 5 ≡ 1 (mod 23).

Da bi cio broj a bio invertibilan po modulu b, potrebno je da a i b budu uzajamno prosti, tako da, kada bi se pronašao NZD veći od 1, moglo bi se zaključiti da takav modularni inverz ne postoji. Primjetimo da su jednačine koje definišu vrijednosti za x_i nezavisne od jednačina koje definišu vrijednosti y_i, i da Bezuov identitet na kraju:

$r_{k}=ax_{k}+by_{k}$

dozvoljava dedukciju y_k, kada znamo x_k. Stoga možemo izostaviti vrednosti y_i iz računanja (mada mogu biti korisne za proveru računskih grešaka). Ovo je naročito važno za primene, poput modularnog inverza, koje zahtevaju vrednost samo jednog Bezuovog koeficijenta.

Rekurzivna metoda

Ovaj metod pokušava da riješi originalnu jednačinu direktno, redukovanjem djelioca i djeljenika postepeno, od prvog do poslednjeg reda, što zatim može biti zamijenjeno trivijalnom vrijednošću i može da funkcioniše unazad u traganju za rješenjem.

Razmotrimo originalnu jednakost:

120	x	+	23	y	=	1
(5×23 + 5)	x	+	23	y	=	1
23	(5x + y)	+	5	x	=	1
...
1	xk	+	0	yk	=	1

Primijetimo da jednakost ostaje neizmenjena nakon razlaganja originalnog dijeljenika u smislu djelioca sa ostatkom, i pregrupisavanja uslova. Ukoliko imamo rješenje jednakosti u drugom redu, onda možemo da idemo unazad i tražimo h i u kao što je i traženo. Iako još uvijek nemamo rješenje za drugi red, primijetimo kako magnituda uslova opada (120 i 23 u 23 i 5). Stoga, ako nastavimo ovo da primjenjujemo, na kraju ćemo doći do poslednjeg reda, koji očigledno ima (1, 0) kao trivijalno rješenje. Onda možemo da idemo unazad i postepeno nalazimo h i u.

Deljenik	=	Količnik	x	Djelilac	+	Ostatak
120	=	5	x	23	+	5
23	=	4	x	5	+	3
...

U svrhu objašnjavanja ovog metoda, neće biti prikazan čitav postupak. Umjesto toga, neki koraci koji se ponavljaju će biti opisani da bi se prikazao princip koji stoji u pozadini ove metode. Počnimo tako što ćemo ponovo ispisivati redove iz prve tabele koristeći algoritam dijeljenja, koncentrišući se na djeljenik ovog puta (pošto ćemo deljenik zamjenjivati).

120	x0	+	23	y0	=	1
(5×23+5)	x0	+	23	y0	=	1
23	(5x0+y0)	+	5	x0	=	1
23	x1	+	5	y1	=	1
(4×5+3)	x1	+	5	y1	=	1
5	(4x1+y1)	+	3	x1	=	1
5	x2	+	3	y2	=	1

Pretpostavimo da nam je već dato x2 = 2 i y2 = −3 , što zaista jeste validno rešenje. x1 = y2 = −3 Rešimo 4x1 + y1 = x2 menjanjem x1 = −3, što daje y1 = 2 − 4(−3) = 14 x0 = y1 = 14 Rešimo 5x0 + y0 = x1 menjanjem x0 = 14, dakle y0 = −3 − 5(14)= −73

Tablična metoda

Tablični metod, takođe poznat i kao "Magična kutija", je vjerovatno najjednostavniji metod koji se može obaviti pomoću olovke i papira. Sličan je iterativnom metodu, mada ne zahtjeva direktno korišćenje algebre. Neka 

$NZD(a,b)$ označava ostatak  r u dijeljenju 

$a=bq+r$ . Osnovna ideja je da razmišljamo o lancu jednakosti

$NZD(a,b)=NZD(b,ostatak(a,b))=...=NZD(c,1)$

kao o sekvenci delilaca (a,b) ostatak (a,b), ...., 1. U postojećem primjeru imamo sekvencu 120, 23, 5, 3, 2, 1. Bilo koji element u ovom lancu se može zapisati kao linearna kombinacija originalnih a i b, a što je najznačajnije, poslednji element NZD(a,b) , može biti ovako zapisan. Tablični metod uključuje održavanje tabele za svakog djelioca, zapisane kao linearna kombinacija. Algoritam počinje sljedećom tabelom:

x	y	d
1	0	120
0	1	23

Elementi u d koloni tabele će biti djelioci u sekvenci. Svako $d_i$ se može predstaviti kao linearna kombinacija a i vrijednosti su očigledne u prva dva reda tabele, i predstavljaju upravo a i b. Da bismo izračunali $d_i$ za bilo koje $i > 2$, primjetimo da

$d_{i}=$ostatak $(d_{i-2},d_{i-1})$

Pretpostavimo  $d_{i}=d_{i-2}-k_{i-1}d_{i-1})$. Onda mora biti

$d_{i}=x_{i}a+y_{i}b$

Ovo je lako algebarski potvrditi jednostavnom zamjenom.

Zapravo, obavljanje tabličnog metoda je jednostavnije nego što se to da zaključiti iz gorenavedenih jednakosti. Za nalaženje trećeg reda u tabeli u primeru, samo primetimo da se 120 podeljeno sa 23 pojavljuje 5 puta sa ostatkom. To nam daje k, multiplikativni faktor za ovaj red. Sada, svaka od vrednosti u tabeli je vrednost dva reda iznad nje, minus k puta vrednost odmah ispod nje. Ovo korektno vodi do

$x_{3}=1-5*0=1$

$y_{3}=0-5*1=-5$i

$d_{3}=120-5*23=5$

Nakon ponavljanja ovog metoda u cilju nalaženja svakog reda tabele (primjetimo da su ostatak zapisan u tabeli i multiplikativni faktor dva različita broja!), konačne vrijednosti za x i y će riješiti

$ax+by=NZD(a,b)$

x	y	d	k
1	0	120
0	1	23	5
1	-5	5	4
-4	21	3	1
5	-26	2	1
-9	47	1	2

Ovaj metod je jednostavan i zahtjeva samo ponovljenu primjenu jednog pravila, i daje odgovor u poslednjem redu bez traganja unazad. Primjetimo takođe da ako imamo namjeru da pronađemo modularni inverz za a po modulu b i dobijemo negativno h, treba da dodamo modul b h-u da bismo ga doveli u opseg. Ovo ne utiče na validnost rješenja, pošto imamo

$a(x+b)+b(y-a)=ax+by$

Formalni opis algoritma

Iterativna metoda

Prema rutini algebre o proširenju i grupisanju kao uslovima (pogledati poslednju sekciju), dobijen je sljedeći algoritam za iterativnu metodu:

1. Primjeniti Euklidov algoritam, i postaviti q_n (n počinje od 1) kao konačnu listu količnika u dijeljenju.
2. Inicijalizovati x₀, x₁ na 1, 0, i y₀, y₁ na 0,1.
   1. Zatim za svako i dokle god je q_i definisano,
   2. Izračunati x_i+1 = x_i-1 − q_ix_i
   3. Izračunati y_i+1 = y_i−1 − q_iy_i
   4. Ponavljati gore navedeno nakon povećanja vrijednosti i za 1
3. Odgovori su od drugog do poslednjeg od x_n i y_n.

Pseudo-kod za ovaj metod je prikazan ispod:

function prosireni_nzd(a, b)
    x := 0    poslednji_x := 1
    y := 1    poslednji_y := 0
    while b ≠ 0
        kolicnik := a div b
        (a, b) := (b, a mod b)
        (x, poslednji_x) := (poslednji_x - kolicnik*x, x)
        (y, poslednji_y) := (poslednji_y - kolicnik*y, y)       
    return (poslednji_x, poslednji_y)

Dodatni koraci su neophodni kada radimo sa negativnim a i/ili b.

Rekurzivna metoda

Rješavajući opšti slučaj jednakosti u poslednjoj odgovarajućoj sekciji, naredni algoritam daje rješenje. Ako je dat bilo koji par nenegativnih cijelih brojeva a i b, on pronalazi cjelobrojne vrijednosti h i u takve da je ax + by nenegativno i deli a i b, što implicira da je to najveći zajednički djelilac za a i b.

1. Ako je b = 0, algoritam se završava, a kao povratnu vrijednost vraća x = 1, y = 0.
2. Inače:
   • Odrediti količnik q i ostatak r dijeljenjem a sa b koristeći algoritam cjelobrojnog dijeljenja
   • Zatim rekurzivno pronaći koeficijente s, t takve da bs + rt dijeli i b i r.
   • Konačno, algoritam vraća rješenje x = t, i y = s − qt.

Ovo se u pseudo kodu može zapisati ovako:

function prosireni_nzd(a, b)
    if b == 0
        return (1, 0)
    else
        (q, r) := podeli (a, b)
        (s, t) := prosireni_nzd(b, r)
        return (t, s - q * t)

Ovim pretpostavljamo da postoji postupak dijeljenja koji vraća (količnik, ostatak) par (moglo bi se staviti q := a divb, a zatim r = a − b * q).

Dokaz korektnosti

Neka su a i b nenegativni cijeli brojevi. Želimo da dokažemo da se algoritam završava, i vraća (h, u) takve da ax + by dijeli i a i b. Nastavljamo indukcijom po b.

• Ako je b = 0, algoritam odmah staje sa izvršavanjem sa h = 1 i u = 0, tako da ax + by = a; ovo je očigledno nenegativno i dijeli i a i 0 (jer je a₀ = 0).
• Inače, neka su q, r dobijeni dijeljenjem a sa b kao u opisu algoritma, tako da a = bq + r i r < b prema svojstvima Euklidovog dijeljenja.
  • Nejednakost r < b znači da možemo da primjenimo induktivnu pretpostavku za (b,r) na mestu (a,b), i ovo nam garantuje da se rekurzivna primena završava.
  • Neka su (s,t) vrijednosti koje vraća; prema indukciji znamo da je bs + rt nenegativno i dijeli i b i r.
  • Sada algoritam vraća x = t i y = s − qt. Imamo ax + by = at + b(s − qt) = bs + (a − bq)t = bs + rt, što je (još uvijek) nenegativno i dijeli i b i r. Isti broj stoga dijeli r + bq = a, čime se dokaz završava.

Dokaz pokazuje da se rekurzivni algoritam može prilagoditi za rad sa proizvoljnim cijelim brojevima  a, b neznatnom modifikacijom: u završnom slučaju b = 0 bi trebalo da ispita znak od a, i ako je negativan vraća h = -1, umjesto h = 1, da bi se osiguralo da ax + by uvijek bude nenegativna vrijednost. Ovim se pretpostavlja da izabrani algoritam dijeljenja funkcioniše ako su a i/ili b negativni, i osigurava da je |r| < |b| u svim slučajevima (uobičajena specifikacija Euklidovog dijeljenja zapravo zahteva da r bude nenegativno, ali ovo nije neophodno u dokazu, kao što jeste sada po rekurenciji po |b|).

Izračunavanje multiplikativnog inverza u konačnom polju

Prošireni Euklidov algoritam se takođe može koristiti za računanje modularnog multiplikativnog inverza u konačnom polju.

Pseudokod

S obzirom da nesvodljiva polinomijalna funkcija f(x) definiše polje, i element a(x) čiji inverz želimo, oblik algoritma koji odgovara određivanju inverza je dat u nastavku. PAŽNjA: ostatak() i kolicnik() su funkcije drugačije od niski ostatak[] i kolicnik[]. ostatak() se odnosi na ostatak pri dijeljenju dva broja, a kolicnik() na celobrojni količnik pri dijeljenju dva broja. Dijeljenje (sa ostatkom) se mora izračunati pod uslovima polinomijalne aritmetike a ne "normalnih" brojeva.

pseudokod:

ostatak[1] := f(x)
ostatak[2] := a(x)
pomocni[1] := 0
pomocni[2] := 1
i := 2
while ostatak[i] > 1
    i := i + 1
    ostatak[i] := ostatak(ostatak[i-2] / ostatak[i-1])
    kolicnik[i] := kolicnik(ostatak[i-2] / ostatak[i-1])
    pomocni[i] := -kolicnik[i] * pomocni[i-1] + pomocni[i-2]
inverz := pomocni[i]

Napomena: u nekim konačnim poljima, na primer GF(2ⁿ), ), operacije dodavanja (+) i oduzimanja (−) su iste. Kao posljedica, neki algoritmi namjenjeni takvim poljima neće prikazivati znak minus pije

-quotient[i].

Primjer

Na primer, ako se konačno polje GF(2⁸) definiše polinomijalno sa

f(x) = x⁸ + x⁴ + x³ + x + 1, i 

x⁶ + x⁴ + x + 1 = {53},

u big endian heksadecimalnoj notaciji, je element čiji inverz želimo, izvršivši algoritam dobijamo sljedeće:

i	ostatak[i]	kolicnik[i]	pomocni[i]
1	x8 + x4 + x3 + x + 1		0
2	x6 + x4 + x + 1		1
3	x2	x2 + 1	x2 + 1
4	x + 1	x4 + x2	x6 + x4 + x4 + x2 + 1
5	1	x + 1	x7 + x6 + x3 + x2 + x2 + x + 1 + 1
6	0	x + 1

Napomena: Dodavanje u binarnom konačnom polju je XOR.

Prema ovome, inverz je x⁷ + x⁶ + x³ + x = {CA}, što se može potvrditi množenjem ova dva elementa.

Slučaj više od dva broja

Možemo riješiti slučaj više od dva broja iterativno. Prvo, pokažemo da NZD(a,b,c)=NZD(NZD(a,b),c). Da bismo dokazali ovo, neka je d=NZD(a,b,c) . Po definiciji nzd-a,  je deelilac od  a i b. Prema tome NZD(a,b)=kd  za neko k . Slično  je d delilac za c tako da je c=jd za neko j. Neka je . Prema našoj konstrukciji u - a, ud/a,b,c,  ali pošto je d  najveći delilac u -a je jedinica. I pošto je ud =NZD(NZD(a.b).c)rezultat je dokazan.

Tako, ako na+mb=NZD(a,b), onda postoje  x i  y takvi da  

xNZD(a,b)+yc=NZD(NZD(a,b),c) pa će krajnja jednačina biti

x(na+mb)+yc=(xn)a+(xm)b+yc=NZD(a.b,c)

Da bi primjenili na n brojeva koristimo indukciju

NZD(a_1,,a₂,...,a_n)=NZD(a₁,NZD(a₂,.....,NZD(a_n-1,a_n)))...)

uz direktno praćenje jednakosti.

Literatura

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3 of section 31.2: Greatest common divisor.

Spoljašnje veze

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)