Prošireni Euklidov algoritam

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

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:

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[uredi]

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[uredi]

Ovaj metod računa izraze oblika za ostatak u svakom koraku Euklidovog algoritma. Svaki uzastopni broj može biti zapisan kao ostatak pri deljenju prethodna dva takva broja, čiji ostatak može biti izražen koristeći ceo količnik qi tog deljenja prema formuli:

Kada se zamene vrednosti, ovo daje:

što može da se zapiše kao

Prve dve vrednosti su polazni argumenti za algoritam:

Dakle, početni koeficijenti su x1 = 1, y1 = 0, x2 = 0, i y2 = 1, a drugi su dati kao

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 xi nezavisne od jednačina koje definišu vrednosti yi, i da Bezuov identitet na kraju:

dozvoljava dedukciju yk, kada znamo xk. Stoga možemo izostaviti vrednosti yi 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[uredi]

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 xk + 0 yk = 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 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
  1. Pretpostavimo da nam je već dato x2 = 2 i y2 = −3 , što zaista jeste validno rešenje.
  2. x1 = y2 = −3
  3. Rešimo 4x1 + y1 = x2 menjanjem x1 = −3, što daje y1 = 2 − 4(−3) = 14
  4. x0 = y1 = 14
  5. Rešimo 5x0 + y0 = x1 menjanjem x0 = 14, dakle y0 = −3 − 5(14)= −73

Tablična metoda[uredi]

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 označava ostatak u deljenju . Osnovna ideja je da razmišljamo o lancu jednakosti

kao o sekvenci delilaca . 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, , 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 koloni tabele će biti delioci u sekvenci. Svako se može predstaviti kao linearna kombinacija

and vrednosti su očigledne u prva dva reda tabele, i predstavljaju upravo i . Da bismo izračunali za bilo koje , primetimo da

Pretpostavimo . Onda mora biti

i

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

,
, i

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 i će rešiti :

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 .

Formalni opis algoritma[uredi]

Iterativna metoda[uredi]

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

  1. Primeniti Euklidov algoritam, i postaviti qn (n počinje od 1) kao konačnu listu količnika u deljenju.
  2. Inicijalizovati x0, x1 na 1, 0, i y0, y1 na 0,1.
    1. Zatim za svako i dokle god je qi definisano,
    2. Izračunati xi+1 = xi-1qixi
    3. Izračunati yi+1 = yi−1qiyi
    4. Ponavljati gorenavedeno nakon povećanja vrednosti i za 1
  3. Odgovori su od drugog do poslednjeg od xn i yn.

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[uredi]

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.

  1. Ako je b = 0, algoritam se završava, a kao povratnu vrednost vraća x = 1, y = 0.
  2. 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 = sqt.

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 = ab * q).

Dokaz korektnosti[uredi]

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 a0 = 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 = sqt. Imamo ax + by = at + b(sqt) = bs + (abq)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[uredi]

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

Pseudokod[uredi]

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(2n), ), operacije dodavanja (+) i oduzimanja (−) su iste. Kao posledica, neki algoritmi namenjeni takvim poljima neće prikazivati znak minus pre
-quotient[i].

Primer[uredi]

Na primer, ako se konačno polje GF(28) definiše polinomijalno sa f(x) = x8 + x4 + x3 + x + 1, i x6 + x4 + 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   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[1].

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

Slučaj više od dva broja[uredi]

Možemo rešiti slučaj više od dva broja iterativno. Prvo, pokažemo da . Da bismo dokazali ovo, neka je . Po definiciji nzd-a, je delilac od i . Prema tome za neko . Slično, je delilac za tako da je za neko . Neka je . Prema našoj konstrukciji -a, ali pošto je najveći delilac -a je jedinica. I pošto je rezultat je dokazan.

Tako, ako , onda postoje i takvi da pa će krajnja jednačina biti

Da bi primenili na n brojeva koristimo indukciju

uz direktno praćenje jednakosti.

Reference[uredi]

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

Literatura[uredi]

  • 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[uredi]