Back

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




                                     

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

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

a x + b y = n z d a, b. {\displaystyle ax+by=nzda,b.}

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

                                     

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

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

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

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

                                     

1.1. Неформална формулација алгоритма Итеративна метода

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

r i = r i − 2 − q i r i − 1. {\displaystyle r_{i}=r_{i-2}-q_{i}r_{i-1}.\,}

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

r i = a x i − 2 + b y i − 2 − q i a x i − 1 + b y i − 1, {\displaystyle 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. {\displaystyle r_{i}=ax_{i-2}-q_{i}x_{i-1}+by_{i-2}-q_{i}y_{i-1}.\,}

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

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

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

x i = x i − 2 − q i x i − 1, {\displaystyle x_{i}=x_{i-2}-q_{i}x_{i-1},\,} y i = y i − 2 − q i y i − 1. {\displaystyle y_{i}=y_{i-2}-q_{i}y_{i-1}.\,}

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

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

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

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

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

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

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

N Z D = r k = a x k + b y k {\displaystyle {\mathit {NZD}}=r_{k}=ax_{k}+by_{k}\,}

дозвољава дедукцију y k, када знамо x k. Стога можемо изоставити вредности y i из рачунања мада могу бити корисне за проверу рачунских грешака. Ово је нарочито важно за примене, попут модуларног инверза, које захтевају вредност само једног Безуовог коефицијента.

                                     

1.2. Неформална формулација алгоритма Рекурзивна метода

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

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

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

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



                                     

1.3. Неформална формулација алгоритма Таблична метода

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

n z d a, b = n z d b, ostatak ⁡ a, b) = ⋯ = n z d c, 1 {\displaystyle nzda,b=nzdb,\operatorname {ostatak} a,b)=\dots =nzdc,1}

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

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

d i = x i ⋅ a + y i ⋅ b. {\displaystyle d_{i}=x_{i}\cdot a+y_{i}\cdot b.}

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

d i = ostatak ⁡ d i − 2, d i − 1. {\displaystyle d_{i}=\operatorname {ostatak} d_{i-2},d_{i-1}.}

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

x i = x i − 2 − k i − 1 ⋅ x i − 1 {\displaystyle x_{i}=x_{i-2}-k_{i-1}\cdot x_{i-1}} и y i = y i − 2 − k i − 1 ⋅ y i − 1. {\displaystyle y_{i}=y_{i-2}-k_{i-1}\cdot y_{i-1}.}

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

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

x 3 = 1 − 5 ⋅ 0 = 1 {\displaystyle x_{3}=1-5\cdot 0=1}, y 3 = 0 − 5 ⋅ 1 = − 5 {\displaystyle y_{3}=0-5\cdot 1=-5}, и d 3 = 120 − 5 ⋅ 23 = 5. {\displaystyle d_{3}=120-5\cdot 23=5.}

Након понављања овог метода у циљу налажења сваког реда табеле приметимо да су остатак записан у табели и мултипликативни фактор два различита броја!, коначне вредности за x {\displaystyle x} и y {\displaystyle y} ће решити a x + b y = n z d a, b {\displaystyle ax+by=nzda,b\,}:

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

                                     

2.1. Формални опис алгоритма Итеративна метода

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

  • Израчунати x i+1 = x i-1 − q i x i
  • Применити Еуклидов алгоритам, и поставити q n почиње од 1 као коначну листу количника у дељењу.
  • Понављати горенаведено након повећања вредности i за 1
  • Израчунати y i +1 = y i −1 − q i y i
  • Иницијализовати x 0, x 1 на 1, 0, и y 0, y 1 на 0.1.
  • Затим за свако i докле год је q i дефинисано,
  • Одговори су од другог до последњег од x n и y n.

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

function prosireni_nzda, 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.

                                     

2.2. Формални опис алгоритма Рекурзивна метода

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

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

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

function prosireni_nzda, b if b == 0 return 1, 0 else q, r:= podeli a, b s, t:= prosireni_nzdb, r return t, s - q * t

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



                                     

2.3. Формални опис алгоритма Доказ коректности

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

  • Нека су s, t вредности које враћа; према индукцији знамо да је bs + rt ненегативно и дели и b и r.
  • Неједнакост r < b значи да можемо да применимо индуктивну претпоставку за b, r на месту a, b, и ово нам гарантује да се рекурзивна примена завршава.
  • Иначе, нека су q, r добијени дељењем са b као у опису алгоритма, тако да a = bq + r и r < b према својствима Еуклидовог дељења.
  • Ако је b = 0, алгоритам одмах стаје са извршавањем са х = 1 и у = 0, тако да ax + by = a ; ово је очигледно ненегативно и дели и а и 0 јер је а 0 = 0.
  • Сада алгоритам враћа 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 | у свим случајевима.

                                     

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

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

Псеудокод

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

Пример

На пример, ако се коначно поље GF2 8 дефинише полиномијално са f x = x 8 + x 4 + x 3 + x + 1, и x 6 + x 4 + x + 1 = {53}, у big endian хексадецималној нотацији, је елемент чији инверз желимо, извршивши алгоритам добијамо следеће:

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

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

                                     

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

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

Тако, ако n a + m b = n z d a, b {\displaystyle na+mb=nzda,b}, онда постоје x {\displaystyle x} и y {\displaystyle y} такви да x n z d a, b + y c = n z d a, b, c {\displaystyle xnzda,b+yc=nzda,b,c} па ће крајња једначина бити

x n a + m b + y c = x n a + x m b + y c = n z d a, b, c. {\displaystyle xna+mb+yc=xna+xmb+yc=nzda,b,c.\,}

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

n z d = n z d a 1, n z d a 2, n z d a 3, …, n z d a n − 1, a n) …), {\displaystyle nzda_{1},a_{2},\dots,a_{n}=nzda_{1},\,nzda_{2},\,nzda_{3},\dots,nzda_{n-1}\,a_{n})\dots),}

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