Проширени Еуклидов алгоритам

Проширени Еуклидов алгоритам, поред проналажења највећег заједничког делиоца целих бројева а и b, што ради обични Еуклидов алгоритам, такође налази целе бројеве х и у (од којих је углавном један негативан) који задовољавају Безуов став:

ax+by=nzd(a,b).

Проширени Еуклидов алгоритам је посебно користан када су а и b узајамно прости, пошто је х модуларни мултипликативни инверз од a по модулу b, а y је модуларни мултипликативни инверз од b по модулу a. Ово има значај у израчунавању кључа у RSA алгоритму за шифровање јавног кључа; налажење целобројног експонента за дешифровање d који је модуларни мултипликативни инверз изабраног експонента е по модулу φ(n), где су e и φ(n) узајамно прости.

Неформална формулација алгоритма

Дељеник	Делилац	Количник	Остатак
120	23	5	5
23	5	4	3
5	3	1	2
3	2	1	1
2	1	2	0

Да бисмо илустровали проширење Еуклидовог алгоритма, размотримо израчунавање нзд(120, 23), који је приказан у табели лево. Приметимо да је количник у сваком дељењу забележен као и остатак.

У овом случају, делилац у последњем реду (који је једнак 1) нам говори да је нзд 1; то јест, 120 и 23 су узајамно прости (такође се називају и релативно прости). Због једноставности, изабрани примери су пар узајамно простих; али у општијем случају нзд-а који није 1, ово слично функционише.

Постоје два метода у наставку, од којих оба користе алгоритам целобројног дељења као подпоступак, од којих ће сваки бити засебно дискутован.

Итеративна метода

Овај метод рачуна изразе облика $r_{i}=ax_{i}+by_{i}$ за остатак у сваком кораку $i$ Еуклидовог алгоритма. Сваки узастопни број $r_{i}$ може бити записан као остатак при дељењу претходна два таква броја, чији остатак може бити изражен користећи цео количник q_i тог дељења према формули:

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

Када се замене вредности, ово даје:

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

што може да се запише као

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

Прве две вредности су полазни аргументи за алгоритам:

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

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

Дакле, почетни коефицијенти су x₁ = 1, y₁ = 0, x₂ = 0, и y₂ = 1, а други су дати као

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

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

Израз за последњи не-нула остатак даје жељени резултат, пошто овај метод рачуна сваки остатак у односу на а и b, као што је и жељено.

Пример: израчунати НЗД од 120 и 23

Рачунање тече према наредној табели:

Корак	Количник	Остатак	Замена	Комбиновани услови
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	Крај алгоритма

У последњем реду стоји 1 = 120 × −9 + 23 × 47, што је тражено решење: x = −9 и y = 47.

Пошто је НЗД 1, ово такође значи да 47 даје мултипликативни инверз од 23 по модулу 120, а такође по модулу 23, -9 (или 14, који представљају исти елемент) даје мултипликативни инверз од 120 (или, еквивалентно, од 5).

47 × 23 ≡ 1 (mod 120) и такође −9 × 120 ≡14 × 5 ≡ 1 (mod 23).

Да би цео број a био инвертибилан по модулу b, потребно је да a и b буду узајамно прости, тако да, када би се пронашао НЗД већи од 1, могло би се закључити да такав модуларни инверз не постоји. Приметимо да су једначине које дефинишу вредности за x_i независне од једначина које дефинишу вредности y_i, и да Безуов идентитет на крају:

{\mathit {NZD}}=r_{k}=ax_{k}+by_{k}\,

дозвољава дедукцију y_k, када знамо x_k. Стога можемо изоставити вредности y_i из рачунања (мада могу бити корисне за проверу рачунских грешака). Ово је нарочито важно за примене, попут модуларног инверза, које захтевају вредност само једног Безуовог коефицијента.

Рекурзивна метода

Овај метод покушава да реши оригиналну једначину директно, редуковањем делиоца и дељеника постепено, од првог до последњег реда, што затим може бити замењено тривијалном вредношћу и може да функционише уназад у трагању за решењем.

Размотримо оригиналну једнакост:

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

Приметимо да једнакост остаје неизмењена након разлагања оригиналног дељеника у смислу делиоца са остатком, и прегруписавања услова. Уколико имамо решење једнакости у другом реду, онда можемо да идемо уназад и тражимо х и у као што је и тражено. Иако још увек немамо решење за други ред, приметимо како магнитуда услова опада (120 и 23 у 23 и 5). Стога, уколико наставимо ово да примењујемо, на крају ћемо доћи до последњег реда, који очигледно има (1, 0) као тривијално решење. Онда можемо да идемо уназад и постепено налазимо х и у.

Дељеник	=	Количник	x	Делилац	+	Остатак
120	=	5	x	23	+	5
23	=	4	x	5	+	3
...

У сврху објашњавања овог метода, неће бити приказан читав поступак. Уместо тога, неки кораци који се понављају ће бити описани да би се приказао принцип који стоји у позадини ове методе. Почнимо тако што ћемо поново исписивати редове из прве табеле користећи алгоритам дељења, концентришући се на дељеник овог пута (пошто ћемо дељеник замењивати).

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

Претпоставимо да нам је већ дато x₂ = 2 и y₂ = −3 , што заиста јесте валидно решење.
x₁ = y₂ = −3
Решимо 4x₁ + y₁ = x₂ мењањем x₁ = −3, што даје y₁ = 2 − 4(−3) = 14
x₀ = y₁ = 14
Решимо 5x₀ + y₀ = x₁ мењањем x₀ = 14, дакле y₀ = −3 − 5(14)= −73

Таблична метода

Таблични метод, такође познат и као "Магична кутија", је вероватно најједноставнији метод који се може обавити помоћу оловке и папира. Сличан је итеративном методу, мада не захтева директно коришћење алгебре. Нека $\operatorname {nzd} (a,b)$ означава остатак $r$ у дељењу $a=bq+r$ . Основна идеја је да размишљамо о ланцу једнакости

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

као о секвенци делилаца $a,b,\operatorname {ostatak} (a,b),\dots ,1$ . У постојећем примеру имамо секвенцу 120, 23, 5, 3, 2, 1. Било који елемент у овом ланцу се може записати као линеарна комбинација оригиналних a и b, а што је најзначајније, последњи елемент, $nzd(a,b)$ , може бити овако записан. Таблични метод укључује одржавање табеле за сваког делиоца, записане као линеарна комбинација. Алгоритам почиње следећом табелом:

x	y	d
1	0	120
0	1	23

Елементи у $d$ колони табеле ће бити делиоци у секвенци. Свако $d_{i}$ се може представити као линеарна комбинација

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

$x$ and $y$ вредности су очигледне у прва два реда табеле, и представљају управо $a$ и $b$ . Да бисмо израчунали $d_{i}$ за било које $i>2$ , приметимо да

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

Претпоставимо $d_{i}=d_{i-2}-k_{i-1}\cdot d_{i-1}$ . Онда мора бити

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

и

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

Ово је лако алгебарски потврдити једноставном заменом.

Заправо, обављање табличног метода је једноставније него што се то да закључити из горенаведених једнакости. За налажење трећег реда у табели у примеру, само приметимо да се 120 подељено са 23 појављује 5 пута са остатком. То нам даје k, мултипликативни фактор за овај ред. Сада, свака од вредности у табели је вредност два реда изнад ње, минус k пута вредност одмах испод ње. Ово коректно води до

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

,

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

, и

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

Након понављања овог метода у циљу налажења сваког реда табеле (приметимо да су остатак записан у табели и мултипликативни фактор два различита броја!), коначне вредности за $x$ и $y$ ће решити $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

Овај метод је једноставан и захтева само поновљену примену једног правила, и даје одговор у последњем реду без трагања уназад. Приметимо такође да уколико имамо намеру да пронађемо модуларни инверз за а по модулу b и добијемо негативно х, треба да додамо модул b х-у да бисмо га довели у опсег. Ово не утиче на валидност решења, пошто имамо $a(x+b)+b(y-a)=ax+by$ .

Формални опис алгоритма

Итеративна метода

Према рутини алгебре о проширењу и груписању као условима (погледати последњу секцију), добијен је следећи алгоритам за итеративну методу:

Применити Еуклидов алгоритам, и поставити q_n (n почиње од 1) као коначну листу количника у дељењу.
Иницијализовати x₀, x₁ на 1, 0, и y₀, y₁ на 0,1.
1. Затим за свако i докле год је q_i дефинисано,
2. Израчунати x_i+1 = x_i-1 − q_ix_i
3. Израчунати y_i+1 = y_i−1 − q_iy_i
4. Понављати горенаведено након повећања вредности i за 1
Одговори су од другог до последњег од x_n и y_n.

Псеудо-код за овај метод је приказан испод:

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)

Додатни кораци су неопходни када радимо са негативним a и/или b.

Рекурзивна метода

Решавајући општи случај једнакости у последњој одговарајућој секцији, наредни алгоритам даје решење. Ако је дат било који пар ненегативних целих бројева а и b, он проналази целобројне вредности х и у такве да је ax + by ненегативно и дели а и b, што имплицира да је то највећи заједнички делилац за а и b.

Ако је b = 0, алгоритам се завршава, а као повратну вредност враћа x = 1, y = 0.
Иначе:
- Одредити количник q и остатак r дељењем а са b користећи алгоритам целобројног дељења
- Затим рекурзивно пронаћи коефицијенте s, t такве да bs + rt дели и b и r.
- Коначно, алгоритам враћа решење x = t, и y = s − qt.

Ово се у псеудо коду може записати овако:

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)

Овим претпостављамо да постоји поступак дељења који враћа (количник, остатак) пар (могло би се ставити q := a div b, а затим r = a − b * q).

Доказ коректности

Нека су a и b ненегативни цели бројеви. Желимо да докажемо да се алгоритам завршава, и враћа (х, у) такве да ax + by дели и а и b. Настављамо индукцијом по b.

Ако је b = 0, алгоритам одмах стаје са извршавањем са х = 1 и у = 0, тако да ax + by = a; ово је очигледно ненегативно и дели и а и 0 (јер је а₀ = 0).
Иначе, нека су q, r добијени дељењем а са b као у опису алгоритма, тако да a = bq + r и r < b према својствима Еуклидовог дељења.
- Неједнакост r < b значи да можемо да применимо индуктивну претпоставку за (b,r) на месту (a,b), и ово нам гарантује да се рекурзивна примена завршава.
- Нека су (s,t) вредности које враћа; према индукцији знамо да је bs + rt ненегативно и дели и b и r.
- Сада алгоритам враћа x = t и y = s − qt. Имамо ax + by = at + b(s − qt) = bs + (a − bq)t = bs + rt, што је (још увек) ненегативно и дели и b и r. Исти број стога дели r + bq = a, чиме се доказ завршава.

Доказ показује да се рекурзивни алгоритам може прилагодити за рад са произвољним целим бројевима а, b незнатном модификацијом: у завршном случају b = 0 би требало да испита знак од а, и ако је негативан враћа х = -1, уместо х = 1, да би се осигурало да ax + by увек буде ненегативна вредност. Овим се претпоставља да изабрани алгоритам дељења функционише ако су а и/или b негативни, и осигурава да је |r| < |b| у свим случајевима (уобичајена спецификација Еуклидовог дељења заправо захтева да r буде ненегативно, али ово није неопходно у доказу, као што јесте сада по рекуренцији по |b|).

Израчунавање мултипликативног инверза у коначном пољу

Проширени Еуклидов алгоритам се такође може користити за рачунање модуларног мултипликативног инверза у коначном пољу.

Псеудокод

С обзиром да несводљива полиномијална функција f(x) дефинише поље, и елемент a(x) чији инверз желимо, облик алгоритма који одговара одређивању инверза је дат у наставку. ПАЖЊА: ostatak() и kolicnik() су функције другачије од ниски ostatak[] и kolicnik[]. ostatak() се односи на остатак при дељењу два броја, а kolicnik() на целобројни количник при дељењу два броја. Дељење (са остатком) се мора израчунати под условима полиномијалне аритметике а не "нормалних" бројева.

псеудокод:

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]

Напомена: у неким коначним пољима, на пример GF(2ⁿ), ), операције додавања (+) и одузимања (−) су исте. Као последица, неки алгоритми намењени таквим пољима неће приказивати знак минус пре
-quotient[i].

Пример

На пример, ако се коначно поље GF(2⁸) дефинише полиномијално са f(x) = x⁸ + x⁴ + x³ + x + 1, и x⁶ + x⁴ + x + 1 = {53}, у big endian хексадецималној нотацији, је елемент чији инверз желимо, извршивши алгоритам добијамо следеће:

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

Напомена: Додавање у бинарном коначном пољу је XOR^[1].

Према овоме, инверз је x⁷ + x⁶ + x³ + x = {CA}, што се може потврдити множењем ова два елемента.

Случај више од два броја

Можемо решити случај више од два броја итеративно. Прво, покажемо да $nzd(a,b,c)=nzd(nzd(a,b),c)$ . Да бисмо доказали ово, нека је $d=nzd(a,b,c)$ . По дефиницији nzd-а, $d$ је делилац од $a$ и $b$ . Према томе $nzd(a,b)=kd$ за неко $k$ . Слично, $d$ је делилац за $c$ тако да је $c=jd$ за неко $j$ . Нека је $u=nzd(k,j)$ . Према нашој конструкцији $u$ -a, $ud|a,b,c$ али пошто је $d$ највећи делилац $u$ -a је јединица. И пошто је $ud=nzd(nzd(a,b),c)$ резултат је доказан.

Тако, ако $na+mb=nzd(a,b)$ , онда постоје $x$ и $y$ такви да $xnzd(a,b)+yc=nzd(a,b,c)$ па ће крајња једначина бити

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

Да би применили на n бројева користимо индукцију

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

уз директно праћење једнакости.

Референце

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

Литература

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.

Спољашње везе

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]