Utökad Euklids algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 mars 2022; kontroller kräver 7 redigeringar .

Den utökade euklidiska algoritmen är en förlängning av den euklidiska algoritmen , som beräknar, förutom den största gemensamma divisorn (GCD) av heltal a och b , även Bezout- kvotskoefficienter , det vill säga heltal x och y , så att

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

Algoritmen validerar [ eftersom gcd är det enda talet som både uppfyller ekvationen och delar de inmatade talen. Algoritmen gör det också möjligt att beräkna kvoterna för a och b med deras största gemensamma divisor nästan utan extra kostnad.

Den utökade euklidiska algoritmen hänvisar också till en mycket liknande algoritm för att beräkna den största gemensamma divisorn för polynom och beräkna Bezout-kvotskoefficienterna för två polynom i en variabel.

Den utökade Euklidiska algoritmen är särskilt användbar när a och b är coprime . Under dessa förhållanden är x den reciproka modulen för a modulo b och y är den reciproka modulen för b modulo a . På liknande sätt tillåter den utökade Euklids algoritm för polynom att beräkna det reciproka i algebraiska förlängningar och i synnerhet i finita fält av icke-enkel ordning. Därför används båda de utökade euklidiska algoritmerna i stor utsträckning i kryptografi . I synnerhet är beräkning av den inversa modulo ett väsentligt steg för att härleda ett nyckelpar i RSA -krypteringsmetoden för publik nyckel.

Beskrivning

Euklids standardalgoritm utförs av successiva divisioner med en rest , medan kvoten inte används, bara resten bevaras. Den utökade algoritmen använder också divisionskvoter. Mer exakt består den euklidiska standardalgoritmen för talen a och b som indata av att beräkna en sekvens av kvotienter och en sekvens av rester så att ${\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{(detta definierar }}q_ {i})\\&\,\,\,\vdots \end{aligned}}

Den främsta egenskapen med delning med rest är att ojämlikheten till höger bestämmer det unika hos både för och $q_{i}$ $r_{i+1}$ $r_{i-1}$ $r_{i}.$

Beräkningen stannar när vi når noll rest . Den största gemensamma delaren är då lika med den sista resten som inte är noll $r_{k+1}$ $r_{k}.$

Utökad Euclids algoritm fungerar på liknande sätt men lägger till två andra sekvenser

{\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{ och }}0&\leqslant r_{i+1}<|r_{i}|&{\text{(detta definierar }}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}}

Beräkningen stannar också när och som ett resultat vi får $r_{k+1}=0$

$r_{k}$ är lika med den största gemensamma divisorn för ingångsvärdena , och $a=r_{0}$ $b=r_{1}.$
Bezout-koefficienterna är lika med och , det vill säga ${\displaystyle s_{k))$ $t_{k},$ ${\text{gcd}}(a,b)=r_{k}=as_{k}+bt_{k}$
Kvotienterna för att dividera a och b med deras största gemensamma divisor ges av och $s_{k+1}=\pm {\frac {b}({\text{gcd}}(a,b)))$ $t_{k+1}=\pm {\frac {a}({\text{gcd}}(a,b)))$

Dessutom, om båda siffrorna a och b är positiva och , då ${\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\lfloor {\frac {a}{2{\text{gcd}}(a,b)))\right\rfloor

för , där betyder heltalsdelen av talet x , det vill säga det största heltal som inte överstiger x . $0\leqslant i\leqslant k,$ $\lgolv x\rgolv$

Det följer att paret av Bezout-koefficienter som ges av den utökade Euklidiska algoritmen är det minsta paret av Bezout-koefficienter, eftersom det är det enda paret som uppfyller båda olikheterna ovan.

Det följer också att algoritmen kan exekveras utan risk för heltalsöversvämning av ett program som använder heltal av en fast storlek som är större än både a och b .

Exempel

Följande tabell visar hur den utökade euklidiska algoritmen fungerar med inmatningstalen 240 och 46 . Den största gemensamma delaren är det sista elementet som inte är noll, 2 i den återstående kolumnen. Beräkningen slutar på rad 6 eftersom resten är 0 . Bezout-koefficienter visas i de två sista cellerna i den näst sista raden. Det är lätt att kontrollera att −9 × 240 + 47 × 46 = 2 . Slutligen är de två sista värdena 23 och -120 i den sista raden, upp till ett tecken, kvoterna för ingångsvärdena 46 och 240 dividerat med den största gemensamma divisorn 2 .

index i	kvoten q i −1	resten r i	är jag	t i
0		240	ett	0
ett		46	0	ett
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
fyra	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

Bevis

Eftersom sekvensen är en minskande sekvens av icke-negativa heltal (med början från i = 2). Då måste algoritmen sluta någon gång , vilket bevisar att algoritmen så småningom kommer att avslutas. $0\leqslant r_{i+1}<|r_{i}|,$ ${\displaystyle r_{i))$ $r_{k+1}=0.$

Eftersom den största gemensamma divisorn kommer att vara densamma för och Detta visar att den största gemensamma divisorn av ingångarna kommer att vara densamma som för Detta bevisar att är den största gemensamma divisorn av a och b . (Fram till denna punkt är beviset detsamma som för den klassiska Euklidiska algoritmen.) $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))$

Eftersom och , vi har för i = 0 och 1. Relationen bevisas genom induktion för alla : $a=r_{0}$ $b=r_{1},$ ${\displaystyle 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}.

Sedan och är Bezout-koefficienter. ${\displaystyle s_{k))$ $t_k$

Tänk på matrisen

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

Återkommande relationer kan skrivas om i matrisform

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

Matrisen är identitetsmatrisen och dess determinant är en. Determinanten för matrisen längst till höger här är −1. Det följer att determinanten är i synnerhet, för vi har Om vi betraktar detta som en Bézout-relation, får vi det och är coprime . Ovanstående relation och Euklids lemma visar att b delar , det vill säga för något heltal d . Dividera med förhållandet , får vi att alltså, och är coprime heltal som är kvoter för att dividera a och b med en gemensam divisor, som är deras största gemensamma divisor eller dess motsats . $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}$

För att bevisa det sista påståendet, anta att a och b är positiva och . Sedan , och om , kan det ses att sekvenserna s och t för ( a , b ) i den utökade algoritmen är, upp till inledande nollor och ettor, sekvenserna t och s för ( b , a ). Definitionerna visar då att fallet ( a , b ) reduceras till fallet ( b , a ). Således, utan förlust av allmänhet, kan vi anta att . ${\text{gcd}}(a,b)\neq \min(a,b)$ $a\neq b$ $a<b$ $a>b$

Du kan se att det är lika med 1, och (som finns på grund av ) är negativt. Således byter tecken och strikt ökar i absolut värde, vilket följer av induktion från definitionen och det faktum att för . Fallet för är tillfredsställt eftersom . Detsamma gäller efter de första terminerna av samma skäl. Dessutom är det lätt att se det (om a och b är positiva och ). Sedan $s_{2}$ ${\displaystyle s_{3))$ ${\text{gcd}}(a,b)\neq \min(a,b)$ $si}$ $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}|.

Detta, i sällskap med det faktum att det inte är mindre i absolut värde än någon tidigare eller respektive, kompletterar beviset. ${\displaystyle s_{k},t_{k))$ $si}$ $t_{i}$

En förlängning av Euklids algoritm för polynom

För polynom i en variabel med koefficienter i ett fält fungerar allt på liknande sätt, inklusive Euklids division, Bezouts relation och utökade Euklids algoritm. Den första skillnaden är att i den euklidiska divisionen och i algoritmen ska olikheten ersättas med olikheten av grader. Resten förblir densamma, ersätt bara heltalen med polynom. $0\leqslant r_{i+1}<|r_{i}|$ $\deg r_{i+1}<\deg r_{i}.$

Den andra skillnaden ligger i gränserna för storleken på Bézout-koefficienterna som ges av den utökade Euklidiska algoritmen, vilka är mer exakta när det gäller polynom, vilket leder till följande sats.

Om a och b är två polynom som inte är noll, ger den utökade euklidiska algoritmen ett unikt par polynom ( s , t ) så att

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

och

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

Den tredje skillnaden är att för polynom definieras den största gemensamma divisorn fram till multiplikation med en konstant som inte är noll. Det finns flera sätt att bestämma den största gemensamma divisorn unikt.

I matematik krävs vanligtvis att den största gemensamma divisorn är ett reducerat polynom . För att uppnå detta räcker det att dela alla delar av resultatet med den ledande faktorn . Detta gör det möjligt att, om a och b är coprime, få 1 på höger sida av Bezouts ojämlikhet. Annars får vi en konstant som inte är noll. I datoralgebra har polynom vanligtvis heltalskoefficienter, och detta sätt att normalisera den största gemensamma divisorn resulterar i ett stort antal bråk. $r_{k}.$

Ett annat sätt att normalisera den största gemensamma divisorn för fallet med heltalskoefficienter är att dela utpolynomet med gcd för polynomets koefficienter för att få en primitiv största gemensamma divisor. Om ingångspolynomen är coprime ger normalisering den största gemensamma divisorn på 1. Nackdelen med detta tillvägagångssätt är det stora antalet bråk som måste beräknas och förenklas. $r_{k},$

Det tredje tillvägagångssättet är att utöka algoritmen för att beräkna mellansekvenser av pseudoresidualer ( subresults ) på samma sätt som att utöka den euklidiska algoritmen till den utökade euklidiska algoritmen. Detta tillåter, att börja med ett polynom med heltalskoefficienter, att erhålla polynom med heltalskoefficienter under beräkningsprocessen. Dessutom förblir varje beräknad återstod ett delresultat. I synnerhet, om polynomen är coprime, blir Bézout-relationen till $r_{i}$

as+bt=\operatörsnamn {Res} (a,b),

där betyder resultanten för a och b . I denna form har Bezout-relationen ingen nämnare i formeln. Om vi dividerar allt med resultanten får vi den klassiska Bezout-relationen med en explicit gemensam nämnare för de rationella talen som förekommer. $\operatorname {Res} (a,b)$

Pseudokod

För att implementera ovanstående algoritm bör det noteras att endast de två sista värdena av de indexerade variablerna behövs vid varje steg. För att spara minne bör därför varje indexerad variabel ersättas med bara två variabler.

För enkelhetens skull använder följande algoritm (och andra algoritmer i den här artikeln) parallella tilldelningar . I programmeringsspråk som inte stöder denna funktion måste parallell tilldelning göras med en extra variabel. Till exempel den första uppgiften

(gammal_r, r) := (r, gammal_r - kvot * r)

ekvivalent med

prov:= r; r := gammal_r - kvot × prov; gammal_r := prov;

och liknande för andra parallella uppdrag. Detta leder till följande kod:

funktion utökad_gcd(a, b) (gammal_r, r) := (a, b) (gamla_s, s) := (1, 0) (gammal_t, t) := (0, 1) medan r ≠ 0 gör kvot := gammal_r div r (gammal_r, r) := (r, gammal_r − kvot × r) (gamla_s, s) := (s, gamla_s − kvot × s) (gammal_t, t) := (t, gammal_t − kvot × t) output "Bezout-koefficienter:", (old_s, old_t) output "största gemensamma divisor:", old_r output "kvotienter av gcd:", (t, s)

Kvotienterna för att dividera a och b med sin största gemensamma divisor, som också finns i utgången, kan ha fel tecken. Detta är lätt att fixa i slutet av beräkningen, men görs inte här för att förenkla koden. På liknande sätt, om antingen a eller b är noll och det andra talet är negativt, är den största gemensamma divisorn i utgången negativ, så alla tecken i utgången måste vändas om.

Slutligen noterar vi att Bezout-relationen kan lösas relativt för given . Då skulle en optimering för algoritmen ovan endast beräkna sekvensen (vilket leder till Bézout-koefficienten ) och beräkna värdet i slutet av algoritmen: $axe+by={\text{gcd}}(a,b)$ $y$ $a,b,x,{\text{gcd}}(a,b)$ ${\displaystyle s_{k))$ $x$ $y$

funktion utökad_gcd(a, b) s:= 0; gamla_s := 1 r:=b; old_r := a medan r ≠ 0 gör kvot := gammal_r div r (gammal_r, r) := (r, gammal_r − kvot × r) (gamla_s, s) := (s, gamla_s − kvot × s) om b ≠ 0 så bezout_t := (gammal_r − gammal_s × a) div b annat bezout_t := 0 output "bezout coefficients:", (old_s, bezout_t) output "största gemensamma divisor:", old_r

Men i många fall kommer detta inte att vara en riktig optimering - den tidigare algoritmen är okänslig för spill när man använder heltal i maskinen (d.v.s. heltal med en fast övre gräns på representationen), multiplicering av old_s * a vid beräkning av bezout_t kan orsaka ett spill , vilket begränsar optimeringen till endast indata som inte överstiger hälften av den maximala storleken på heltal. Om heltal av obegränsad storlek används, växer tiden som krävs för multiplikation och division kvadratiskt med storleken på heltalen. Av detta följer att "optimering" ersätter en sekvens av multiplikationer/divisioner av små tal med en enkel multiplikation/division, vilket kräver mer exekveringstid än de operationer den ersätter tillsammans.

Förenkla division

Divisionabär i kanoniskt förenklad form om a och b är coprime och b är positivt. Denna kanoniska förenklade form kan erhållas genom att ersätta de tre utdataraderna med pseudokod

om s = 0 , mata ut "Division med noll" om s < 0 då s := − s ; t := − t ( för att undvika nolldelare ) om s = 1 utgång - t ( för att undvika divisorer på 1) -t _s

Beviset för denna algoritm bygger på det faktum att s och t är två coprime heltal så att , och sedan . För att få en kanoniskt förenklad form räcker det att ändra tecknet för att få en positiv divisor. $as+bt=0$ ${\frac {a}{b}}=-{\frac {t}{s}}$

Om b delar en jämnt, utför algoritmen bara en iteration, och vi har s = 1 i slutet av algoritmen. Detta är det enda fallet där utdata är ett heltal.

Beräkning av inversen i modulära strukturer

Den utökade Euklidiska algoritmen är ett viktigt sätt att beräkna reciproka i modulära strukturer, vanligtvis modulära heltal och algebraiska fältförlängningar . Ett viktigt exempel på det senare fallet är ändliga fält av icke-enkel ordning.

Heltal modulo

Om n är ett positivt heltal kan ringen Z / n Z identifieras med mängden {0, 1, ..., n -1} av rester av division med en rest av n , addition och multiplikation tar resten av division med n av resultaten av addition och multiplikation av heltal. Ett element a Z / n Z har en invers (dvs ett inverterbart element ) om det är relativt primtal till n . I synnerhet, om n är primtal , har a en invers om den inte är noll (modulo n ). Det vill säga, Z / n Z är ett fält om och endast om n är primtal.

Bezouts relation säger att a och n är coprime om och endast om det finns heltal s och t så att

ns+at=1

Jämförelse modulo n ger

at\equiv 1\mod n.

Då är t , eller mer exakt, resten av att dividera t med n , lika med det reciproka av en modulo n .

För att anpassa den utökade Euklidiska algoritmen till detta problem, bör det noteras att Bezout-koefficienten för n inte behövs, och därför finns det inget behov av att beräkna den. För att få resultatet som ett positivt tal mindre än n kan du också använda det faktum att heltal t som tillhandahålls av algoritmen uppfyller relationen . Det vill säga om , kan du lägga till n i slutet. Detta resulterar i pseudokod där ingångsvärdet n är ett heltal större än 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

Algebraiska fälttillägg

Den utökade Euklidiska algoritmen är också huvudverktyget för att beräkna inverserna av algebraiska fältförlängningar . Ett viktigt fall, som ofta används inom kryptografi och kodningsteori , är fallet med ändliga fält av icke-enkel ordning. Faktum är att om p är enkel och q = p d , är ordningsfältet q en algebraisk förlängning av primtalsfältet med p element bildade av roten av ett irreducerbart polynom av grad d .

Den algebraiska förlängningen L av fältet K som genereras av roten av ett irreducerbart polynom p av grad d kan identifieras med kvotringen och dess element är i ett bijektivt förhållande med polynom med grad mindre än d . Addition i L är additionen av polynom. Multiplikation i L är resten av divisionen med resten med p av produkten av polynom. För att slutföra aritmetiken i L återstår alltså bara att bestämma hur de inversa elementen ska beräknas. Detta görs med den utökade Euklidiska algoritmen. $K[X]/\langle p\rangle ,$

Algoritmen är mycket lik den ovan för att beräkna den modulära inversen. Det finns två huvudsakliga skillnader - för det första behövs inte den näst sista raden, eftersom de resulterande Bezout-koefficienterna alltid har en grad mindre än d . För det andra kan den största gemensamma delaren som uppstår om indata är coprime polynom vara vilket element som helst av K som inte är noll . Denna Bézout-koefficient (ett polynom har vanligtvis en positiv grad) ska multipliceras med den reciproka av detta element i K . I pseudokoden (nedan) är p ett polynom av grad större än ett, och a är ett 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 Exempel

Låt till exempel polynomet definiera det slutliga fältet och vara det element vars invers ska hittas. Sedan visas algoritmens funktion i tabellen nedan. Kom ihåg att i ett ordningsfält har vi - z = z och z + z = 0 för något eller element z i fältet). Eftersom 1 är det enda elementet som inte är noll i GF(2), finns det inget behov av att justera den sista raden i pseudokoden. $p=x^{8}+x^{4}+x^{3}+x+1$ $GF(2^{8})$ $a=x^{6}+x^{4}+x+1$ $2^{n}$

steg	privat	r, nyare	s, nyheter	t, vattensalamander
		$p=x^{8}+x^{4}+x^{3}+x+1$	ett	0
		$a=x^{6}+x^{4}+x+1$	0	ett
ett	$x^{2}+1$	$x^{2}=pa(x^{2}+1)$	ett	$x^{2}+1=0-1\ gånger (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)$
fyra	x +1	$0=(x+1)-1\ gånger (x+1)$	$x^{6}+x^{4}+x+1=(x^{4}+x^{2})-(x+1)(x^{5}+x^{4} +x^{3}+x^{2}+1)$

Det inversa elementet är alltså , vilket bekräftas genom att multiplicera de två elementen och ta resten över p från resultatet. $x^{7}+x^{6}+x^{3}+x$

Fallet med fler än två siffror

Du kan hantera fallet med fler än två nummer iterativt. Låt oss först visa det . För beviset, låt oss sätta . Per definition är gcd en divisor av och . Sen för vissa . På samma sätt är en divisor , så för vissa . Låt . Genom konstruktion , , men eftersom det är den största divisorn, är en inverterbar del av . Och sedan är resultatet bevisat. ${\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)$

Således, om , det vill säga och , sådan att , så att den slutliga ekvationen blir $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).\,

För att gå till n tal använder vi induktion

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

Se även

Anteckningar

Litteratur

Donald Knuth. Kapitel 4 // Konsten att programmera datorer . — Addison-Wesley. - T. 2. .
- Översatt av Donald Knuth. Konsten att programmera. - 1998. - V. 2. Erhållna algoritmer.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . avsnitt 31.2: Största gemensamma delare. // Introduktion till algoritmer . - Andra upplagan. - MIT Press och McGraw-Hill, 2001. - P. 859-861. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: Konstruktion och analys , 3:e upplagan = Introduktion till algoritmer, tredje upplagan. - M. : "Williams" , 2013. - 1328 sid. - ISBN 978-5-8459-1794-2 .

Länkar

Källa för formen av algoritmen som används för att bestämma multiplikativ invers i GF(2^8)

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm