Kibővített Euklidész algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. március 9-én felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

A kiterjesztett euklideszi algoritmus az Euklideszi algoritmus kiterjesztése , amely az a és b egész számok legnagyobb közös osztóján (GCD) kívül Bezout-arány együtthatókat is kiszámít , azaz x és y egész számokat úgy, hogy

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

Az algoritmus az -t érvényesíti , mert a gcd az egyetlen szám, amely teljesíti az egyenletet és osztja a bemeneti számokat. Az algoritmus lehetővé teszi a és b hányadosának kiszámítását is a legnagyobb közös osztójukkal, szinte többletköltség nélkül.

A kiterjesztett euklideszi algoritmus egy nagyon hasonló algoritmusra is hivatkozik a polinomok legnagyobb közös osztójának kiszámítására , valamint két polinom Bezout-arány együtthatóinak kiszámítására egy változóban.

A kiterjesztett Euklidész algoritmus különösen akkor hasznos, ha a és b koprím . Ilyen feltételek mellett x a modulo b modulo reciproka , y pedig b modulo a modulus reciproka . Hasonlóképpen, a kibővített Euklidész-algoritmus polinomokra lehetővé teszi a reciprok kiszámítását algebrai kiterjesztésekben , és különösen nem egyszerű sorrendű véges mezőkben . Ezért mindkét kiterjesztett Euclid algoritmust széles körben használják a kriptográfiában . Különösen az inverz modulo kiszámítása lényeges lépés egy kulcspár származtatásához az RSA nyilvános kulcsú titkosítási módszerben.

Leírás

A standard euklidészi algoritmust egymást követő osztásokkal hajtjuk végre maradékkal , miközben a hányadost nem használjuk, csak a maradékot őrizzük meg. A kiterjesztett algoritmus az osztás hányadosait is használja. Pontosabban, a standard euklideszi algoritmus az a és b számokra bemenetként abból áll , hogy hányadosok sorozatát és maradékok sorozatát számítják ki úgy, hogy ${\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{(ez határozza meg a }}q_ {i})\\&\,\,\,\vdots \end{aligned}}

A maradékkal való osztás fő tulajdonsága , hogy a jobb oldali egyenlőtlenség határozza meg mind a for , mind az egyediségét $q_{i}$ $r_{i+1}$ $r_{i-1}$ $r_{i}.$

A számítás leáll, ha elérjük a nulla maradékot . A legnagyobb közös osztó ekkor egyenlő az utolsó nem nulla maradékkal $r_{k+1}$ $r_{k}.$

A kiterjesztett Euklidész algoritmus hasonlóan működik, de két másik sorozatot ad hozzá

{\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}&{\ szöveg{ és }}0&\leqslant r_{i+1}<|r_{i}|&{\text{(ez határozza meg a }}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{igazított}}

A számítás is leáll, amikor és ennek eredményeként megkapjuk $r_{k+1}=0$

$r_{k}$ egyenlő a bemeneti értékek legnagyobb közös osztójával , és $a=r_{0}$ $b=r_{1}.$
A Bezout együtthatók egyenlőek és , azaz ${\displaystyle s_{k))$ $t_{k},$ ${\text{gcd}}(a,b)=r_{k}=as_{k}+bt_{k}$
Az a és b legnagyobb közös osztójukkal való osztásának hányadosait és adja meg $s_{k+1}=\pm {\frac {b}({\text{gcd}}(a,b)))$ $t_{k+1}=\pm {\frac {a}({\text{gcd}}(a,b)))$

Sőt, ha mind a , mind a b szám pozitív és , akkor ${\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

mert , ahol az x szám egész részét jelenti , vagyis azt a legnagyobb egész számot, amely nem haladja meg az x -et . $0\leqslant i\leqslant k,$ $\lfloor x\rfloor$

Ebből következik, hogy a kiterjesztett Euklidész algoritmus által adott Bezout-együttható pár a Bezout-együttható minimális párja , mivel ez az egyetlen pár, amely kielégíti mindkét fenti egyenlőtlenséget.

Ebből az is következik, hogy az algoritmust egész szám túlcsordulás veszélye nélkül végrehajthatja egy olyan program , amely rögzített méretű egész számokat használ, amelyek nagyobbak, mint a és b .

Példa

A következő táblázat bemutatja, hogyan működik a kiterjesztett Euklidész algoritmus a 240 és 46 bemeneti számokkal . A legnagyobb közös osztó az utolsó nem nulla elem, 2 a maradék oszlopban. A számítás a 6. sorban ér véget, mert a maradék 0 . A Bezout együtthatók az utolsó előtti sor utolsó két cellájában jelennek meg. Könnyen ellenőrizhető, hogy −9 × 240 + 47 × 46 = 2 . Végül az utolsó sor utolsó két értéke 23 és -120 egy előjelig a 46 és 240 bemeneti értékek hányadosa, osztva a legnagyobb közös osztóval 2 .

index i	hányados q i −1	maradék r i	s i	t i
0		240	egy	0
egy		46	0	egy
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
négy	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

Bizonyítás

Mivel a sorozat nemnegatív egész számok csökkenő sorozata ( i = 2-től kezdve). Ekkor az algoritmusnak egy ponton le kell állnia Ez azt bizonyítja, hogy az algoritmus végül leáll. $0\leqslant r_{i+1}<|r_{i}|,$ ${\displaystyle r_{i))$ $r_{k+1}=0.$

Mivel a legnagyobb közös osztója ugyanaz lesz és esetén Ez azt mutatja, hogy a bemenetek legnagyobb közös osztója ugyanaz lesz, mint a Ez azt bizonyítja, hogy a és b legnagyobb közös osztója . (Eddig a bizonyítás ugyanaz, mint a klasszikus Eukleidész algoritmusnál.) $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))$

Mivel és , i = 0 és 1 esetén van . Az összefüggést indukcióval bizonyítjuk mindenre : $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}.

Ezután és Bezout együtthatók. ${\displaystyle s_{k))$ $t_k$

Tekintsük a mátrixot

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

Az ismétlődő relációk mátrix alakban átírhatók

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

A mátrix az identitásmátrix, determinánsa pedig egy. A jobb szélső mátrix determinánsa itt −1. Ebből következik, hogy a determináns Konkrétan, mert van Ha ezt Bézout-relációnak tekintjük, akkor azt kapjuk, és coprime . A fenti összefüggés és Eukleidész lemmája azt mutatja, hogy b oszt , azaz valamilyen d egész számra . Az aránnyal osztva azt kapjuk, hogy így, és olyan másodlagos egész számok, amelyek a és b osztó hányadosai egy közös osztóval , amely a legnagyobb közös osztójuk vagy annak ellentéte . $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}$

Az utolsó állítás bizonyításához tegyük fel, hogy a és b pozitív és . Ekkor és ha látható, hogy a kiterjesztett algoritmusban az ( a , b ) s és t sorozatai a kezdő nullákig és egyesekig a ( b , a ) t és s sorozatai . A definíciók ezután azt mutatják, hogy az ( a , b ) eset a ( b , a ) esetre redukálódik . Így az általánosság elvesztése nélkül feltételezhetjük, hogy . ${\text{gcd}}(a,b)\neq \min(a,b)$ $a\neq b$ $a<b$ $a>b$

Látható, hogy egyenlő 1-gyel, és (ami miatt létezik ) negatív. Így előjelet változtat és abszolút értékben szigorúan nő, ami indukcióval következik a definícióból és abból, hogy -re . Az ügy teljesül, mert . Ugyanez igaz az első néhány kifejezés után is ugyanezen okokból. Sőt, könnyen belátható, hogy (ha a és b pozitív és ). Akkor $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}|.

Ez, azzal a ténnyel együtt, hogy abszolút értékben nem kisebb, mint bármelyik korábbi , ill ., kiegészíti a bizonyítást. ${\displaystyle s_{k},t_{k))$ $s_{i}$ $t_{i}$

Az Euklidész-algoritmus polinomokra vonatkozó kiterjesztése

Az egy változóban lévő polinomok, amelyek együtthatói egy mezőben vannak, minden hasonló módon működik, beleértve az Euklidész-osztást, a Bezout-relációt és a kiterjesztett Euklidész algoritmust. Az első különbség az, hogy az euklideszi felosztásban és az algoritmusban az egyenlőtlenséget a fokok egyenlőtlenségével kell helyettesíteni, a többi változatlan marad, csak az egész számokat polinomokra cseréljük. $0\leqslant r_{i+1}<|r_{i}|$ $\deg r_{i+1}<\deg r_{i}.$

A második különbség a kibővített Euklidész-algoritmus által megadott Bézout-együtthatók méretének határaiban rejlik, amelyek polinomok esetén pontosabbak, ami a következő tételhez vezet.

Ha a és b két nem nulla polinom, akkor a kiterjesztett euklideszi algoritmus egyedi polinompárt ( s , t ) ad , így

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

és

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

A harmadik különbség az, hogy polinomok esetében a legnagyobb közös osztó van definiálva egészen a nullától eltérő állandóval való szorzásig. Számos módja van a legnagyobb közös osztó egyedi meghatározásának.

A matematikában általában megkövetelik, hogy a legnagyobb közös osztó egy redukált polinom legyen . Ennek eléréséhez elegendő az eredmény minden elemét elosztani a vezető tényezővel , így ha a és b koprím, akkor a Bezout-egyenlőtlenség jobb oldalán 1-et kaphatunk. Ellenkező esetben nem nulla állandót kapunk. A számítógépes algebrában a polinomok általában egész együtthatókkal rendelkeznek, és a legnagyobb közös osztó normalizálásának ilyen módja nagy számú tört eredményez. $r_{k}.$

Egy másik módszer a legnagyobb közös osztó normalizálására egész együtthatók esetében az, hogy a kimeneti polinomot elosztjuk a polinom együtthatóinak gcd-jével, így kapunk egy primitív legnagyobb közös osztót. Ha a bemeneti polinomok másodprímek, akkor a normalizálás adja az 1 legnagyobb közös osztóját. Ennek a megközelítésnek a hátránya a nagyszámú törtszám, amelyet ki kell számítani és egyszerűsíteni kell. $r_{k},$

A harmadik megközelítés a pszeudoreziduumok ( aleredmények ) közbenső sorozatainak kiszámítására szolgáló algoritmus kiterjesztése, hasonlóan az euklideszi algoritmus kiterjesztéséhez a kiterjesztett euklidészi algoritmusra. Ez lehetővé teszi, hogy egy egész együtthatós polinomtól kezdve egész együtthatós polinomokat kapjunk a számítási folyamat során. Ezenkívül minden számított maradék részeredmény marad. Különösen, ha a polinomok koprímek, akkor a Bézout-reláció átváltozik $r_{i}$

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

ahol a és b eredőjét jelenti . _ Ebben a formában a Bezout-relációnak nincs nevezője a képletben. Ha mindent elosztunk az eredővel, akkor a klasszikus Bezout-relációt kapjuk explicit közös nevezővel a megjelenő racionális számokra. $\operatorname {Res} (a,b)$

Pszeudokód

A fenti algoritmus megvalósításához meg kell jegyezni, hogy minden lépésben csak az indexelt változók utolsó két értékére van szükség. Így a memória megtakarítása érdekében minden indexelt változót csak két változóval kell helyettesíteni.

Az egyszerűség kedvéért a következő algoritmus (és a cikkben szereplő többi algoritmus) párhuzamos hozzárendeléseket használ . Azon programozási nyelveken, amelyek nem támogatják ezt a funkciót, a párhuzamos hozzárendelést egy további változó használatával kell elvégezni. Például az első feladat

(régi_r, r) := (r, régi_r - hányados * r)

egyenértékű

prov := r; r := régi_r - hányados × prov; old_r := prov;

és hasonlóan más párhuzamos feladatokhoz. Ez a következő kódhoz vezet:

függvény extended_gcd(a, b) (régi_r, r) := (a, b) (régi_ek, s) := (1, 0) (régi_t, t) := (0, 1) míg r ≠ 0 do hányados := old_r div r (régi_r, r) := (r, régi_r − hányados × r) (régi_k, s) := (s, old_s − hányados × s) (régi_t, t) := (t, régi_t − hányados × t) kimenet "Bezout coefficients:", (old_s, old_t) kimenet "legnagyobb közös osztó:", old_r kimenet "hányadosok a gcd szerint:", (t, s)

Az a-t és b -t a legnagyobb közös osztójukkal osztó hányadosok , amelyek szintén szerepelnek a kimenetben, rossz előjelűek lehetnek. Ez könnyen javítható a számítás végén, de a kód egyszerűsítése érdekében itt nem. Hasonlóképpen, ha a vagy b nulla, és a második szám negatív, a kimenet legnagyobb közös osztója negatív, ezért a kimenetben minden előjelet meg kell fordítani.

Végül megjegyezzük, hogy a Bezout reláció relatíve megoldható adott . Ekkor a fenti algoritmus optimalizálása csak a sorozatot számítja ki (ami a Bézout együtthatóhoz vezet ), és az algoritmus végén számítja ki az értéket: $ax+by={\text{gcd}}(a,b)$ $y$ ${\megjelenítési stílus a,b,x,{\text{gcd}}(a,b)}$ ${\displaystyle s_{k))$ $x$ $y$

függvény extended_gcd(a, b) s := 0; old_s := 1 r := b; old_r := a míg r ≠ 0 do hányados := old_r div r (régi_r, r) := (r, régi_r − hányados × r) (régi_k, s) := (s, old_s − hányados × s) ha b ≠ 0 , akkor bezout_t := (régi_r − old_s × a) div b else bezout_t := 0 kimenet "bezout coefficients:", (old_s, bezout_t) kimenet "legnagyobb közös osztó:", old_r

Ez azonban sok esetben nem lesz valódi optimalizálás - az előbbi algoritmus érzéketlen a túlcsordulásra, ha egész számokat használ a gépben (azaz olyan egész számokat, amelyeknek fix felső korlátja van a reprezentáción), az old_s * a szorzása a bezout_t kiszámításakor túlcsordulást okozhat , amely az optimalizálást csak olyan bemeneti adatokra korlátozza, amelyek nem haladják meg az egész számok maximális méretének felét. Ha korlátlan méretű egész számokat használunk, a szorzáshoz és osztáshoz szükséges idő négyzetesen növekszik az egész számok méretével. Ebből az következik, hogy az "optimalizálás" kis számok szorzási/osztási sorozatát egyetlen szorzással/osztással helyettesíti, ami több végrehajtási időt igényel, mint az általa helyettesített műveletek együttvéve.

Felosztás egyszerűsítése

Osztályabkanonikus egyszerűsített formában van, ha a és b koprím , és b pozitív. Ezt a kanonikus egyszerűsített formát úgy kaphatjuk meg, hogy a három kimeneti sort pszeudokóddal helyettesítjük

ha s = 0 , akkor "Osztás nullával" adjuk ki, ha s < 0 , akkor s := − s ; t := − t ( a nulla osztók elkerülése érdekében ) ha s = 1 , akkor a kimenet - t ( az 1 osztóinak elkerülése érdekében ) kimenet -t_ _s

Ennek az algoritmusnak a bizonyítása azon a tényen alapul, hogy s és t két társprím egész szám, így , majd . A kanonikusan leegyszerűsített alak megszerzéséhez elegendő az előjelet megváltoztatni, hogy pozitív osztót kapjunk. $as+bt=0$ ${\frac {a}{b}}=-{\frac {t}{s}}$

Ha b egyenlően osztja a egyet, akkor az algoritmus csak egy iterációt hajt végre, és az algoritmus végén s = 1 van. Ez az egyetlen eset, amikor a kimenet egész szám.

Az inverz számítása moduláris struktúrákban

A kiterjesztett Euklideszi algoritmus fontos eszköze a reciprok kiszámításának moduláris struktúrákban, általában moduláris egész számokban és algebrai mezőbővítésekben . Ez utóbbi esetre fontos példa a nem egyszerű sorrendű véges mezők.

Integers modulo

Ha n pozitív egész szám, a Z / n Z gyűrű azonosítható az osztás maradékainak {0, 1, ..., n -1} halmazával n maradékával , az összeadás és a szorzás a maradékot veszi fel. egész számok összeadása és szorzása eredményének osztása n -vel. Egy a Z / n Z elemnek van inverze (vagyis invertálható eleme ), ha n -hez képest relatív prím . Különösen, ha n prím , akkor a -nak van inverze, ha nem nulla (modulo n ). Vagyis Z / n Z akkor és csak akkor mező, ha n prím.

Bezout relációja kimondja, hogy a és n akkor és csak akkor koprím, ha vannak olyan s és t egész számok ,

ns+at=1

Összehasonlítás modulo n ad

at\equiv 1\mod n.

Ekkor t , pontosabban t n -nel való osztásának maradéka egyenlő egy n modulo reciprokával .

A kiterjesztett Eukleidész algoritmus ehhez a problémához való adaptálásához meg kell jegyezni, hogy nincs szükség n Bezout-együtthatójára , ezért nincs szükség kiszámítására. Ahhoz, hogy az eredményt n - nél kisebb pozitív számként kapjuk meg, használhatjuk azt a tényt is, hogy az algoritmus által megadott t egész szám kielégíti a relációt . Vagyis ha , akkor a végére n -t adhatunk . Ez pszeudokódot eredményez, ahol az n bemeneti érték 1-nél nagyobb egész szám. $|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

Algebrai mező kiterjesztések

A kiterjesztett Euclid algoritmus egyben a fő eszköz az algebrai mezőbővítések inverzeinek kiszámításához . Egy fontos eset, amelyet széles körben használnak a kriptográfiában és a kódoláselméletben , a nem egyszerű sorrendű véges mezők esete . Valójában, ha p egyszerű és q = p d , akkor a q rendű mező a prímmező algebrai kiterjesztése p elemmel, amelyet egy d fokú irreducibilis polinom gyöke alkot .

A d fokú irreducibilis p polinom gyökével generált K mező L algebrai kiterjesztése a hányadosgyűrűvel azonosítható, elemei pedig bijektív kapcsolatban állnak a d - nél kisebb polinomokkal . Az L -beli összeadás az összeadás polinomok. L -ben való szorzás a polinomok szorzatának maradékával való osztás maradéka . Így az L -beli aritmetika befejezéséhez már csak az inverz elemek kiszámításának módját kell meghatározni. Ez a kiterjesztett Euclid algoritmussal történik. $K[X]/\langle p\rangle ,$

Az algoritmus nagyon hasonló a fenti moduláris inverz kiszámításához. Két fő különbség van - először is, az utolsó előtti sorra nincs szükség, mivel a kapott Bezout-együtthatók mindig egy fokkal kisebbek, mint d . Másodszor, a Legnagyobb közös osztó, amely akkor jön létre, ha a bemenetek koprím polinomok, a K bármely nullától eltérő eleme lehet . Ezt a Bézout-együtthatót (egy polinomnak általában pozitív foka van) meg kell szorozni ennek az elemnek a K -beli reciprokával . A pszeudokódban (lent) p egynél nagyobb fokú polinom, a pedig egy polinom.

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élda

Például a polinom határozza meg a végső mezőt , és legyen az az elem, amelynek az inverze megtalálható. Ezután az algoritmus működése az alábbi táblázatban látható. Emlékezzünk vissza, hogy egy sorrendi mezőben - z = z és z + z = 0 a mező bármely vagy z elemére . Mivel az 1 a GF(2) egyetlen nem nulla eleme, nincs szükség a pszeudokód utolsó sorának módosítására. $p=x^{8}+x^{4}+x^{3}+x+1$ $GF(2^{8})$ $a=x^{6}+x^{4}+x+1$ $2^{n}$

lépés	magán	r, újabb	s, hírek	t, gőte
		$p=x^{8}+x^{4}+x^{3}+x+1$	egy	0
		$a=x^{6}+x^{4}+x+1$	0	egy
egy	$x^{2}+1$	$x^{2}=pa(x^{2}+1)$	egy	$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)$
négy	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)$

Így az inverz elem , amit megerősítünk, ha a két elemet megszorozzuk , és az eredményből a maradékot p fölé vesszük . $x^{7}+x^{6}+x^{3}+x$

Kettőnél több szám esete

Kettőnél több szám esetét iteratívan kezelheti. Először is mutassuk meg . A bizonyíték kedvéért tegyük fel . Definíció szerint a gcd a és osztója . Aztán néhányért . Hasonlóképpen , osztó , így egyeseknél . Hadd . Szerkezet szerint , de mivel ez a legnagyobb osztó, invertálható eleme a -nek . És mivel , az eredmény bizonyított. ${\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)$

Így, ha , azaz, és , úgy, hogy , így a végső egyenlet az lesz $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).\,

Az n számhoz való lépéshez indukciót használunk

{\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}))) ,\pontok ),

Lásd még

Jegyzetek

Irodalom

Donald Knuth. 4. fejezet // A számítógépes programozás művészete . - Addison-Wesley. - T. 2. .
- Fordította: Donald Knuth. A programozás művészete. - 1998. - V. 2. Megszerzett algoritmusok.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . 31.2 szakasz: Legnagyobb közös osztó. // Bevezetés az algoritmusokba . - Második kiadás. - MIT Press és McGraw-Hill, 2001. - P. 859-861. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmusok: Konstrukció és elemzés , 3. kiadás = Bevezetés az algoritmusokba, harmadik kiadás. - M. : "Williams" , 2013. - 1328 p. - ISBN 978-5-8459-1794-2 .

Linkek

A GF(2^8) multiplikatív inverzének meghatározására használt algoritmus alakjának forrása

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus