Rozšířený Euklidův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. března 2022; kontroly vyžadují 7 úprav .

Rozšířený euklidovský algoritmus je rozšířením Euklidova algoritmu , který počítá kromě největšího společného dělitele (GCD) celých čísel a a b také koeficienty Bezoutova poměru , tedy celá čísla x a y , taková, že

ax+by={\text{gcd}}(a,b).

Algoritmus ověřuje , protože gcd je jediné číslo, které splňuje rovnici a dělí vstupní čísla. Algoritmus také umožňuje vypočítat podíly a a b jejich největším společným dělitelem téměř bez dalších nákladů.

Extended Euclidean Algorithm také odkazuje na velmi podobný algoritmus [ pro výpočet největšího společného dělitele polynomů a výpočet koeficientů Bezoutova poměru dvou polynomů v jedné proměnné.

Rozšířený Euklidův algoritmus je zvláště užitečný, když aab jsou coprime . Za těchto podmínek x je modulo reciproká hodnota a modulo b a y je modulová reciproká hodnota b modulo a . Podobně rozšířený Euklidův algoritmus pro polynomy umožňuje počítat reciproční hodnoty v algebraických rozšířeních a zejména v konečných tělesech nejednoduchého řádu. Proto jsou oba rozšířené euklidovské algoritmy široce používány v kryptografii . Zejména výpočet inverzního modulo je zásadním krokem při odvozování páru klíčů v metodě šifrování veřejného klíče RSA .

Popis

Standardní euklidovský algoritmus se provádí postupným dělením se zbytkem , přičemž kvocient se nepoužívá, zachovává se pouze zbytek . Rozšířený algoritmus také používá podíly dělení. Přesněji řečeno, standardní euklidovský algoritmus pro čísla a a b jako vstup sestává z výpočtu posloupnosti kvocientů a posloupnosti zbytků tak, že ${\displaystyle q_{1},\ldots ,q_{k))$ ${\displaystyle r_{0},\ldots ,r_{k+1))$

{\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i- 1}-q_{i}r_{i}\quad {\text{i}}\quad 0\leqslant r_{i+1}<|r_{i}|\quad {\text{(toto definuje }}q_ {i})\\&\,\,\,\vdots \end{aligned}}

Hlavní vlastností dělení se zbytkem je, že nerovnost napravo určuje jedinečnost obou for a $Qi}$ $r_{i+1}$ $r_{i-1}$ $r_{i}.$

Výpočet se zastaví, když dosáhneme nulového zbytku . Největší společný dělitel je pak roven poslednímu nenulovému zbytku $r_{k+1}$ $r_{k}.$

Rozšířený Euklidův algoritmus funguje podobně, ale přidává dvě další sekvence

{\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}& =1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\ text{ a }}0&\leqslant r_{i+1}<|r_{i}|&{\text{(definuje }}q_{i}{\text{)))\\s_{i+1} &=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\ ,\vdots \end{aligned}}

Výpočet se také zastaví, když a jako výsledek dostaneme $r_{k+1}=0$

$r_{k}$ se rovná největšímu společnému děliteli vstupních hodnot a ${\displaystyle a=r_{0))$ $b=r_{1}.$
Bezoutovy koeficienty se rovnají a , tzn ${\displaystyle s_{k))$ $t_{k},$ ${\text{gcd}}(a,b)=r_{k}=as_{k}+bt_{k}$
Kvocienty dělení a a b jejich největším společným dělitelem jsou dány a $s_{k+1}=\pm {\frac {b}({\text{gcd}}(a,b)))$ $t_{k+1}=\pm {\frac {a}({\text{gcd}}(a,b)))$

Navíc, pokud jsou obě čísla a a b kladná a , pak ${\text{gcd}}(a,b)\neq \min(a,b)$

|s_{i}|\leqslant \left\lfloor {\frac {b}{2{\text{gcd}}(a,b)))\right\rfloor \quad {\text{i}} \quad |t_{i}|\leqslant \left\lpatro {\frac {a}{2{\text{gcd}}(a,b)))\pravé\rpatro

for , kde znamená celočíselnou část čísla x , tedy největší celé číslo nepřesahující x . $0\leqslant i\leqslant k,$ $\lpatro x\rpatro$

Z toho vyplývá, že dvojice Bezoutových koeficientů daná rozšířeným Euklidovým algoritmem je minimální dvojice Bezoutových koeficientů, protože je to jediná dvojice, která splňuje obě výše uvedené nerovnosti.

Z toho také vyplývá, že algoritmus lze provést bez rizika přetečení celého čísla programem používajícím celá čísla pevné velikosti, která je větší než a i b .

Příklad

Následující tabulka ukazuje, jak funguje rozšířený Euklidův algoritmus se vstupními čísly 240 a 46 . Největší společný dělitel je poslední nenulový prvek, 2 ve zbývajícím sloupci. Výpočet končí na řádku 6, protože zbytek je 0 . Bezoutové koeficienty se objeví v posledních dvou buňkách předposledního řádku. Je snadné zkontrolovat, že −9 × 240 + 47 × 46 = 2 . Nakonec poslední dvě hodnoty 23 a −120 posledního řádku, až po znaménko, jsou podíly vstupních hodnot 46 a 240 dělené největším společným dělitelem 2 .

index i	podíl q i −1	zbytek r i	s i	t i
0		240	jeden	0
jeden		46	0	jeden
2	240 ÷ 46 = 5	240 − 5 × 46 = 10	1 − 5 × 0 = 1	0 − 5 × 1 = −5
3	46 ÷ 10 = 4	46 − 4 × 10 = 6	0 − 4 × 1 = −4	1 − 4 × −5 = 21
čtyři	10 ÷ 6 = 1	10 − 1 × 6 = 4	1 − 1 × −4 = 5	−5 − 1 × 21 = −26
5	6 ÷ 4 = 1	6 − 1 × 4 = 2	−4 − 1 × 5 = −9	21 − 1 × −26 = 47
6	4 ÷ 2 = 2	4 − 2 × 2 = 0	5 − 2 × −9 = 23	−26 − 2 × 47 = −120

Důkaz

Protože posloupnost je klesající posloupnost nezáporných celých čísel (počínaje i = 2). Pak se algoritmus musí v určitém bodě zastavit , což dokazuje, že algoritmus nakonec skončí. $0\leqslant r_{i+1}<|r_{i}|,$ ${\displaystyle r_{i))$ $r_{k+1}=0.$

Protože největší společný dělitel bude stejný pro a To ukazuje, že největší společný dělitel vstupů bude stejný jako pro To dokazuje, že je největším společným dělitelem aab . (Až do tohoto bodu je důkaz stejný jako u klasického Euklidova algoritmu.) $r_{i+1}=r_{i-1}-r_{i}q_{i},$ $(r_{i-1},r_{i})$ $(r_{i},r_{i+1}).$ ${\displaystyle a=r_{0},b=r_{1))$ $r_{k},r_{k+1}=0.$ ${\displaystyle r_{k))$

Protože a máme pro i = 0 a 1. Vztah dokazujeme indukcí pro všechny : ${\displaystyle a=r_{0))$ $b=r_{1},$ $as_{i}+bt_{i}=r_{i}$ $i>1$

r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{ i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1} +bt_{i+1}.

Potom a jsou Bezoutovy koeficienty. ${\displaystyle s_{k))$ $t_k$

Zvažte matrici

A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.

Rekurentní vztahy lze přepsat do maticové formy

A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix)).

Matice je matice identity a její determinant je jedna. Determinant matice zcela vpravo je zde −1. Z toho plyne, že determinant je Zejména, protože máme Pokud to považujeme za Bézoutův vztah, dostaneme to a jsou coprime . Výše uvedený vztah a Euklidovo lemma ukazují, že b se dělí , tedy pro nějaké celé číslo d . Dělením poměrem , dostaneme, že Tak, a jsou spoluprvní celá čísla, která jsou kvocienty dělení a a b společným dělitelem, což je jejich největší společný dělitel nebo jeho opak . $A_{1}$ $A_{i}$ $(-1)^{i-1}.$ $i=k+1$ $s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.$ $s_{k+1}$ $t_{k+1}$ $as_{k+1}+bt_{k+1}=0$ $s_{k+1}$ $b=ds_{k+1}$ $s_{k+1}$ $as_{k+1}+bt_{k+1}=0$ $a=-dt_{k+1}.$ $s_{k+1}$ $-t_{k+1}$

K prokázání posledního tvrzení předpokládejme, že aab jsou kladné a . Potom , a if , je vidět, že posloupnosti s a t pro ( a , b ) v rozšířeném algoritmu jsou až po úvodní nuly a jedničky posloupnosti ta s pro ( b , a ) . Definice pak ukazují, že případ ( a , b ) se redukuje na případ ( b , a ). Bez ztráty obecnosti tedy můžeme předpokládat, že . ${\text{gcd}}(a,b)\neq \min(a,b)$ $a\neq b$ $a<b$ $a>b$

Můžete vidět, že se rovná 1 a (které existuje díky ) je záporné. Mění se tedy znaménko a striktně roste v absolutní hodnotě, což vyplývá indukcí z definice a skutečnosti, že pro . Případ pro je splněn, protože . Totéž platí pro po prvních několika termínech ze stejných důvodů. Navíc je to snadné vidět (pokud a a b jsou kladné a ). Pak $s_{2}$ ${\displaystyle s_{3))$ ${\text{gcd}}(a,b)\neq \min(a,b)$ $s_{i}$ $q_{i}\geqslant 1$ $1\leqslant i\leqslant k$ $i=1$ $a>b$ $t_{i}$ $q_{k}\geqslant 2$ ${\text{gcd}}(a,b)\neq \min(a,b)$

|s_{k+1}|=\left|{\frac {b}({\text{GCD))(a,b)))\right|\geqslant 2|s_{k}|\qquad {\text{u}}\qquad |t_{k+1}|=\left|{\frac {a}({\text{gcd}}(a,b)))\right|\geqslant 2|t_ {k}|.

To spolu s faktem, že není v absolutní hodnotě menší než kterýkoli předchozí , resp . ${\displaystyle s_{k},t_{k))$ $s_{i}$ $t_{i}$

Rozšíření Euklidova algoritmu pro polynomy

U polynomů v jedné proměnné s koeficienty v poli funguje vše podobně, včetně Euklidova dělení, Bezoutova vztahu a rozšířeného Euklidova algoritmu. První rozdíl je v tom, že v euklidovském dělení a v algoritmu by měla být nerovnost nahrazena nerovností stupňů , zbytek zůstává stejný, jen nahraďte celá čísla polynomy. $0\leqslant r_{i+1}<|r_{i}|$ $\deg r_{i+1}<\deg r_{i}.$

Druhý rozdíl spočívá v mezích velikosti Bézoutových koeficientů daných rozšířeným Euklidovým algoritmem, které jsou přesnější v případě polynomů, což vede k následující větě.

Jsou-li a a b dva nenulové polynomy, rozšířený euklidovský algoritmus poskytne jedinečnou dvojici polynomů ( s , t ) tak, že

as+bt={\text{gcd}}(a,b)

\deg s<\deg b-\deg({\text{gcd))(a,b)),\quad \deg t<\deg a-\deg({\text{gcd))(a ,b)).

Třetí rozdíl je v tom, že pro polynomy je největší společný dělitel definován až po násobení nenulovou konstantou. Existuje několik způsobů, jak jednoznačně určit největšího společného dělitele.

V matematice se obvykle vyžaduje, aby největší společný dělitel byl redukovaný polynom . K tomu stačí vydělit všechny prvky výsledku vedoucím faktorem . To umožňuje, pokud a a b jsou coprime, dostat 1 na pravou stranu Bezoutovy nerovnosti. Jinak dostaneme nenulovou konstantu. V počítačové algebře mají polynomy obvykle celočíselné koeficienty a tento způsob normalizace největšího společného dělitele má za následek velké množství zlomků. $r_{k}.$

Dalším způsobem, jak normalizovat největšího společného dělitele pro případ celočíselných koeficientů, je vydělit výstupní polynom gcd koeficientů polynomu a získat tak primitivního největšího společného dělitele. Pokud jsou vstupní polynomy coprime, normalizace dává největší společný dělitel 1. Nevýhodou tohoto přístupu je velký počet zlomků, které je nutné vypočítat a zjednodušit. $r_{k},$

Třetím přístupem je rozšíření algoritmu pro výpočet mezilehlých sekvencí pseudozbytků ( subresults ) podobně jako rozšíření Euklidova algoritmu na rozšířený Euklidovský algoritmus. To umožňuje, počínaje polynomem s celočíselnými koeficienty, získat polynomy s celočíselnými koeficienty v procesu výpočtů. Navíc každý vypočítaný zbytek zůstává dílčím výsledkem. Konkrétně, pokud jsou polynomy coprime, pak se Bézoutův vztah změní na $r_{i}$

as+bt=\operatorname {Res} (a,b),

kde znamená výslednici pro a a b . V této podobě nemá Bezoutův vztah ve vzorci jmenovatele. Pokud vše vydělíme výslednicí, dostaneme klasický Bezoutův vztah s explicitním společným jmenovatelem pro uvedená racionální čísla. $\operatorname {Res} (a,b)$

Pseudokód

Pro implementaci výše uvedeného algoritmu je třeba poznamenat, že v každém kroku jsou potřeba pouze poslední dvě hodnoty indexovaných proměnných. Pro úsporu paměti by tedy měla být každá indexovaná proměnná nahrazena pouze dvěma proměnnými.

Pro jednoduchost používá následující algoritmus (a další algoritmy v tomto článku) paralelní přiřazení . V programovacích jazycích, které tuto funkci nepodporují, musí být paralelní přiřazení provedeno pomocí další proměnné. Například první zadání

(starý_r, r) := (r, starý_r - podíl * r)

ekvivalentní

prov := r; r := old_r - kvocient × prov; old_r := prov;

a podobně pro další paralelní zadání. To vede k následujícímu kódu:

funkce extended_gcd(a, b) (starý_r, r) := (a, b) (staré_s, s) := (1, 0) (staré_t, t) := (0, 1) zatímco r ≠ 0 do kvocientu := old_r div r (starý_r, r) := (r, starý_r − podíl × r) (staré_s, s) := (s, staré_s − kvocient × s) (starý_t, t) := (t, starý_t − kvocient × t) výstup "Bezoutovy koeficienty:", (old_s, old_t) výstup "největší společný dělitel:", old_r výstup "podíly podle gcd:", (t, s)

Kvocienty dělení a a b jejich největším společným dělitelem, který je také ve výstupu, mohou mít špatné znaménko. To je snadné opravit na konci výpočtu, ale není to provedeno zde pro zjednodušení kódu. Podobně, pokud a nebo b je nula a druhé číslo je záporné, největší společný dělitel ve výstupu je záporný, takže všechna znaménka ve výstupu je třeba obrátit.

Nakonec si všimneme, že Bezoutovu relaci lze řešit relativně pro daný . Pak by optimalizace pro výše uvedený algoritmus vypočítala pouze sekvenci (což vede k Bézoutově koeficientu ) a vypočítala hodnotu na konci algoritmu: $ax+by={\text{gcd}}(a,b)$ $y$ $a,b,x,{\text{gcd}}(a,b)$ ${\displaystyle s_{k))$ $X$ $y$

funkce extended_gcd(a, b) s:= 0; old_s := 1 r:= b; old_r := a zatímco r ≠ 0 do kvocientu := old_r div r (starý_r, r) := (r, starý_r − podíl × r) (staré_s, s) := (s, staré_s − kvocient × s) jestliže b ≠ 0 then bezout_t := (starý_r − starý_s × a) div b else bezout_t := 0 výstup "bezout koeficienty:", (old_s, bezout_t) výstup "největší společný dělitel:", old_r

V mnoha případech však nepůjde o skutečnou optimalizaci - dřívější algoritmus je necitlivý na přetečení při použití celých čísel ve stroji (tj. celá čísla s pevnou horní hranicí reprezentace), násobení old_s * a při výpočtu bezout_t může způsobit přetečení , který omezuje optimalizaci pouze na vstupní data, která nepřesahují polovinu maximální velikosti celých čísel. Pokud jsou použita celá čísla neomezené velikosti, čas potřebný pro násobení a dělení roste kvadraticky s velikostí celých čísel. Z toho vyplývá, že „optimalizace“ nahrazuje posloupnost násobení/dělení malých čísel jediným násobením/dělením, což vyžaduje více času na provedení než operace, které nahrazuje dohromady.

Zjednodušující rozdělení

DivizeAbje v kanonické zjednodušené formě, pokud aab jsou koprimé a b je kladné . Tuto kanonickou zjednodušenou formu lze získat nahrazením tří řádků výstupu pseudokódem

if s = 0 pak výstup "Dělení nulou" if s < 0 then s := − s ; t := − t ( aby se zabránilo nulovým dělitelům ) pokud s = 1 , pak výstup - t ( aby se zabránilo dělitelům 1) výstup -t _s

Důkaz tohoto algoritmu se opírá o skutečnost, že s a t jsou dvě hlavní celá čísla taková, že , a pak . Pro získání kanonicky zjednodušeného tvaru stačí změnit znaménko a získat kladný dělitel. $as+bt=0$ ${\frac {a}{b}}=-{\frac {t}{s}}$

Pokud b dělí a rovnoměrně, algoritmus provede pouze jednu iteraci a na konci algoritmu máme s = 1 . Toto je jediný případ, kdy je výstupem celé číslo.

Výpočet inverze v modulárních strukturách

Rozšířený Euclidův algoritmus je důležitým prostředkem pro výpočet reciprokých hodnot v modulárních strukturách, obvykle modulárních celých číslech a rozšířeních algebraických polí . Důležitým příkladem druhého případu jsou konečná tělesa nejednoduchého řádu.

Celá čísla modulo

Je-li n kladné celé číslo, lze kruh Z / n Z identifikovat s množinou {0, 1, ..., n -1} zbytků dělení se zbytkem n , sčítání a násobení bere zbytek dělení n výsledků sčítání a násobení celých čísel. Prvek a Z / n Z má inverzní (tj. invertibilní prvek ), pokud je relativně prvočíslo k n . Konkrétně, je-li n prvočíslo , a má inverzní hodnotu, je-li nenulové (modulo n ). To znamená, že Z / n Z je pole právě tehdy, když n je prvočíslo.

Bezoutův vztah říká, že a a n jsou spoluprvní právě tehdy, když existují celá čísla s a t taková, že

ns+at=1

Srovnání modulo n dává

at\equiv 1\mod n.

Pak t , nebo přesněji, zbytek po dělení t n , se rovná převrácené hodnotě modulu n .

Pro přizpůsobení rozšířeného Euklidova algoritmu tomuto problému je třeba poznamenat, že Bezoutův koeficient n není potřeba, a proto jej není třeba počítat. Chcete-li získat výsledek jako kladné číslo menší než n , můžete také použít skutečnost, že celé číslo t poskytnuté algoritmem vyhovuje vztahu . To znamená, že pokud , můžete přidat n na konec. Výsledkem je pseudokód, kde vstupní hodnota n je celé číslo větší než 1. $|t|<n$ $t<0$

function inverse(a, n) t := 0; newt := 1 r := n; newr := a while newr ≠ 0 do quotient := r div newr (t, newt) := (newt, t − quotient × newt) (r, newr) := (newr, r − quotient × newr) if r > 1 then return "не обратимо" if t < 0 then t := t + n return t

Rozšíření algebraických polí

Rozšířený Euclidův algoritmus je také hlavním nástrojem pro výpočet inverzí rozšíření algebraického pole . Důležitým případem, široce používaným v kryptografii a teorii kódování , je případ konečných polí nejednoduchého řádu. Ve skutečnosti, je-li p jednoduché a q = p d , je pole řádu q algebraickým rozšířením prvočísla s p prvky tvořenými kořenem ireducibilního polynomu stupně d .

Algebraické rozšíření L pole K generované kořenem ireducibilního polynomu p stupně d lze identifikovat s podílovým kruhem a jeho prvky jsou v bijektivním vztahu s polynomy stupně menšího než d . Sčítání v L je sčítání polynomů. Násobení v L je zbytek dělení se zbytkem [ p součinu polynomů. K dokončení aritmetiky v L tedy zbývá pouze určit, jak vypočítat inverzní prvky. To se provádí pomocí rozšířeného Euklidova algoritmu. $K[X]/\langle p\rangle ,$

Algoritmus je velmi podobný výše uvedenému pro výpočet modulární inverze. Existují dva hlavní rozdíly - za prvé, předposlední řádek není potřeba, protože výsledné Bezoutovy koeficienty mají vždy stupeň menší než d . Za druhé, největší společný dělitel, který vznikne, pokud jsou vstupy koprime polynomy, může být jakýkoli nenulový prvek K . Tento Bézoutův koeficient (polynom má obvykle kladný stupeň) je třeba vynásobit převrácenou hodnotou tohoto prvku v K . V pseudokódu (níže) je p polynom stupně většího než jedna a a je polynom.

function inverse(a, p) t := 0; newt := 1 r := p; newr := a while newr ≠ 0 do quotient := r div newr (r, newr) := (newr, r − quotient × newr) (t, newt) := (newt, t − quotient × newt) if degree(r) > 0 then return "Either p is not irreducible or a is a multiple of p" return (1/r) × t Příklad

Například nechť polynom definuje konečné pole a je prvkem, jehož inverzní hodnotu má být nalezena. Potom je činnost algoritmu znázorněna v tabulce níže. Připomeňme, že v poli řádu máme - z = z az + z = 0 pro libovolný prvek z pole). Protože 1 je jediný nenulový prvek GF(2), není potřeba upravovat poslední řádek pseudokódu. $p=x^{8}+x^{4}+x^{3}+x+1$ $GF(2^{8})$ $a=x^{6}+x^{4}+x+1$ $2^{n}$

krok	soukromé	r, novější	s, novinky	t, čolek
		$p=x^{8}+x^{4}+x^{3}+x+1$	jeden	0
		$a=x^{6}+x^{4}+x+1$	0	jeden
jeden	$x^{2}+1$	$x^{2}=pa(x^{2}+1)$	jeden	$x^{2}+1=0-1\times (x^{2}+1)$
2	$x^{4}+x^{2}$	$x+1=ax^{2}(x^{4}+x^{2})$	$x^{4}+x^{2}=0-1(x^{4}+x^{2})$	$x^{6}+x^{2}+1=1-(x^{4}+x^{2})(x^{2}+1)$
3	x +1	$1=x^{2}-(x+1)(x+1)$	$x^{5}+x^{4}+x^{3}+x^{2}+1=1-(x+1)(x^{4}+x^{2})$	$x^{7}+x^{6}+x^{3}+x=(x^{2}+1)-(x+1)(x^{6}+x^{2} +1)$
čtyři	x +1	$0=(x+1)-1\times (x+1)$	$x^{6}+x^{4}+x+1=(x^{4}+x^{2})-(x+1)(x^{5}+x^{4} +x^{3}+x^{2}+1)$

Inverzní prvek je tedy , což je potvrzeno vynásobením dvou prvků a převzetím zbytku přes p z výsledku. $x^{7}+x^{6}+x^{3}+x$

Případ více než dvou čísel

Případ více než dvou čísel můžete řešit iterativně. Pojďme si to nejprve ukázat . Pro důkaz uveďme . Podle definice je gcd dělitelem a . Pak pro některé . Podobně je dělitel , takže pro některé . Nechte _ Podle konstrukce je , ale protože je největším dělitelem, invertovatelným prvkem . A od r je výsledek prokázaný. ${\text{gcd}}(a,b,c)={\text{gcd}}({\text{gcd}}(a,b),c)$ $d={\text{gcd}}(a,b,c)$ $d$ $A$ $b$ ${\text{gcd}}(a,b)=kd$ $k$ $d$ $C$ $c=jd$ $j$ $u={\text{gcd}}(k,j)$ $u$ $ud|a,b,c$ $d$ $u$ $ud={\text{gcd}}({\text{gcd}}(a,b),c)$

Tedy, pokud , To je, a , Takový, že , Tak, že konečná rovnice bude $na+mb={\text{gcd}}(a,b)$ $X$ $y$ $x{\text{gcd}}(a,b)+yc={\text{gcd}}(a,b,c)$

x(na+mb)+yc=(xn)a+(xm)b+yc={\text{gcd}}(a,b,c).\,

K přechodu na n čísel používáme indukci

{\text{gcd}}(a_{1},a_{2},\tečky ,a_{n})={\text{gcd}}(a_{1},\,{\text{gcd }}(a_{2},\,{\text{gcd}}(a_{3},\tečky ,{\text{gcd}}(a_{n-1}\,,a_{n}))) ,\tečky ),

Viz také

Poznámky

Literatura

Donald Knuth. Kapitola 4 // Umění počítačového programování . — Addison-Wesley. - T. 2 .
- Přeložil Donald Knuth. Umění programování. - 1998. - V. 2. Získané algoritmy.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . oddíl 31.2: Největší společný dělitel. // Úvod do algoritmů . - Druhé vydání. - MIT Press a McGraw-Hill, 2001. - S. 859-861. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algorithms: Construction and Analysis , 3rd Edition = Introduction to Algorithms, Third Edition. - M. : "Williams" , 2013. - 1328 s. - ISBN 978-5-8459-1794-2 .

Odkazy

Zdroj pro formu algoritmu použitého k určení multiplikativní inverze v GF(2^8)

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin