Prošireni Euklidov algoritam

Prošireni Euklidov algoritam, pored pronalaženja najvećeg zajedničkog delioca celih brojeva a i b, što radi obični Euklidov algoritam, takođe nalazi cele 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

Deljenik	Delilac	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 levo. Primetimo da je količnik u svakom deljenju zabeležen kao i ostatak.

U ovom slučaju, delilac u poslednjem 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 primeri 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 celobrojnog deljenja 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 deljenju prethodna dva takva broja, čiji ostatak može biti izražen koristeći ceo količnik q_i tog deljenja prema formuli:

r_{i}=r_{i-2}-q_{i}r_{i-1}.\,

Kada se zamene vrednosti, 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 dve vrednosti 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.

Primer: izračunati NZD od 120 i 23

Računanje teče prema narednoj tabeli:

Korak	Količnik	Ostatak	Zamena	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 ceo 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. Primetimo da su jednačine koje definišu vrednosti za x_i nezavisne od jednačina koje definišu vrednosti y_i, i da Bezuov identitet na kraju:

{\mathit {NZD}}=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 reši originalnu jednačinu direktno, redukovanjem delioca i deljenika postepeno, od prvog do poslednjeg reda, što zatim može biti zamenjeno trivijalnom vrednošću i može da funkcioniše unazad u traganju za rešenjem.

Razmotrimo originalnu jednakost:

120	x	+	23	y	=	1
(5×23 + 5)	x	+	23	y	=	1
23	(5x + y)	+	5	x	=	1
...
1	x_k	+	0	y_k	=	1

Primetimo da jednakost ostaje neizmenjena nakon razlaganja originalnog deljenika u smislu delioca sa ostatkom, i pregrupisavanja uslova. Ukoliko imamo reš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š uvek nemamo rešenje za drugi red, primetimo kako magnituda uslova opada (120 i 23 u 23 i 5). Stoga, ukoliko nastavimo ovo da primenjujemo, na kraju ćemo doći do poslednjeg reda, koji očigledno ima (1, 0) kao trivijalno rešenje. Onda možemo da idemo unazad i postepeno nalazimo h i u.

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

U svrhu objašnjavanja ovog metoda, neće biti prikazan čitav postupak. Umesto 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 deljenja, koncentrišući se na deljenik ovog puta (pošto ćemo deljenik zamenjivati).

120	x₀	+	23	y₀	=	1
(5×23+5)	x₀	+	23	y₀	=	1
23	(5x₀+y₀)	+	5	x₀	=	1
23	x₁	+	5	y₁	=	1
(4×5+3)	x₁	+	5	y₁	=	1
5	(4x₁+y₁)	+	3	x₁	=	1
5	x₂	+	3	y₂	=	1

Pretpostavimo da nam je već dato x₂ = 2 i y₂ = −3 , što zaista jeste validno rešenje.
x₁ = y₂ = −3
Rešimo 4x₁ + y₁ = x₂ menjanjem x₁ = −3, što daje y₁ = 2 − 4(−3) = 14
x₀ = y₁ = 14
Rešimo 5x₀ + y₀ = x₁ menjanjem x₀ = 14, dakle y₀ = −3 − 5(14)= −73

Tablična metoda

Tablični metod, takođe poznat i kao "Magična kutija", je verovatno najjednostavniji metod koji se može obaviti pomoću olovke i papira. Sličan je iterativnom metodu, mada ne zahteva direktno korišćenje algebre. Neka $\operatorname {nzd} (a,b)$ označava ostatak $r$ u deljenju $a=bq+r$ . Osnovna ideja je da razmišljamo o lancu jednakosti

nzd(a,b)=nzd(b,\operatorname {ostatak} (a,b))=\dots =nzd(c,1)

kao o sekvenci delilaca $a,b,\operatorname {ostatak} (a,b),\dots ,1$ . U postojećem primeru 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 delioca, zapisane kao linearna kombinacija. Algoritam počinje sledećom tabelom:

x	y	d
1	0	120
0	1	23

Elementi u $d$ koloni tabele će biti delioci u sekvenci. Svako $d_{i}$ se može predstaviti kao linearna kombinacija

d_{i}=x_{i}\cdot a+y_{i}\cdot b.

$x$ and $y$ vrednosti 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$ , primetimo da

d_{i}=\operatorname {ostatak} (d_{i-2},d_{i-1}).

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

x_{i}=x_{i-2}-k_{i-1}\cdot x_{i-1}

i

y_{i}=y_{i-2}-k_{i-1}\cdot y_{i-1}.

Ovo je lako algebarski potvrditi jednostavnom zamenom.

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\cdot 0=1

,

y_{3}=0-5\cdot 1=-5

, i

d_{3}=120-5\cdot 23=5.

Nakon ponavljanja ovog metoda u cilju nalaženja svakog reda tabele (primetimo da su ostatak zapisan u tabeli i multiplikativni faktor dva različita broja!), konačne vrednosti za $x$ i $y$ će reš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 zahteva samo ponovljenu primenu jednog pravila, i daje odgovor u poslednjem redu bez traganja unazad. Primetimo takođe da ukoliko imamo nameru 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 reš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 sledeći algoritam za iterativnu metodu:

Primeniti Euklidov algoritam, i postaviti q_n (n počinje od 1) kao konačnu listu količnika u deljenju.
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 gorenavedeno nakon povećanja vrednosti i za 1
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

Rešavajući opšti slučaj jednakosti u poslednjoj odgovarajućoj sekciji, naredni algoritam daje rešenje. Ako je dat bilo koji par nenegativnih celih brojeva a i b, on pronalazi celobrojne vrednosti h i u takve da je ax + by nenegativno i deli a i b, što implicira da je to najveći zajednički delilac za a i b.

Ako je b = 0, algoritam se završava, a kao povratnu vrednost vraća x = 1, y = 0.
Inače:
- Odrediti količnik q i ostatak r deljenjem a sa b koristeći algoritam celobrojnog deljenja
- Zatim rekurzivno pronaći koeficijente s, t takve da bs + rt deli i b i r.
- Konačno, algoritam vraća reš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 deljenja koji vraća (količnik, ostatak) par (moglo bi se staviti q := a div b, a zatim r = a − b * q).

Dokaz korektnosti

Neka su a i b nenegativni celi brojevi. Želimo da dokažemo da se algoritam završava, i vraća (h, u) takve da ax + by deli 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 deli i a i 0 (jer je a₀ = 0).
Inače, neka su q, r dobijeni deljenjem a sa b kao u opisu algoritma, tako da a = bq + r i r < b prema svojstvima Euklidovog deljenja.
- Nejednakost r < b znači da možemo da primenimo induktivnu pretpostavku za (b,r) na mestu (a,b), i ovo nam garantuje da se rekurzivna primena završava.
- Neka su (s,t) vrednosti koje vraća; prema indukciji znamo da je bs + rt nenegativno i deli 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š uvek) nenegativno i deli i b i r. Isti broj stoga deli r + bq = a, čime se dokaz završava.

Dokaz pokazuje da se rekurzivni algoritam može prilagoditi za rad sa proizvoljnim celim 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, umesto h = 1, da bi se osiguralo da ax + by uvek bude nenegativna vrednost. Ovim se pretpostavlja da izabrani algoritam deljenja funkcioniše ako su a i/ili b negativni, i osigurava da je |r| < |b| u svim slučajevima (uobičajena specifikacija Euklidovog deljenja 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 deljenju dva broja, a kolicnik() na celobrojni količnik pri deljenju dva broja. Deljenje (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 posledica, neki algoritmi namenjeni takvim poljima neće prikazivati znak minus pre
-quotient[i].

Primer

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 sledeće:

i	ostatak[i]	kolicnik[i]	pomocni[i]
1	x⁸ + x⁴ + x³ + x + 1		0
2	x⁶ + x⁴ + x + 1		1
3	x²	x² + 1	x² + 1
4	x + 1	x⁴ + x²	x⁶ + x⁴ + x⁴ + x² + 1
5	1	x + 1	x⁷ + x⁶ + x³ + x² + x² + x + 1 + 1
6	0	x + 1

Napomena: Dodavanje u binarnom konačnom polju je XOR^[1].

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 reš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, $d$ je delilac od $a$ i $b$ . Prema tome $nzd(a,b)=kd$ za neko $k$ . Slično, $d$ je delilac za $c$ tako da je $c=jd$ za neko $j$ . Neka je $u=nzd(k,j)$ . 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(a,b,c)$ pa će krajnja jednačina biti

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

Da bi primenili na n brojeva koristimo indukciju

nzd(a_{1},a_{2},\dots ,a_{n})=nzd(a_{1},\,nzd(a_{2},\,nzd(a_{3},\dots ,nzd(a_{n-1}\,,a_{n})))\dots ),

uz direktno praćenje jednakosti.

Reference

^ Robert B Davies (28. 2. 2002). „Exclusive OR (XOR) and hardware random number generators” (PDF).

Literatura

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest & Clifford Stein (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. стр. 859-861. 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)

[1] Robert B Davies (28. 2. 2002). „Exclusive OR (XOR) and hardware random number generators” (PDF).

[1]