Algoritmul extins al lui Euclid

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 martie 2022; verificările necesită 7 modificări .

Algoritmul Euclidian extins este o extensie a algoritmului Euclid , care calculează, pe lângă cel mai mare divizor comun (MCD) al numerelor întregi a și b , și coeficienți ai raportului Bezout , adică numere întregi x și y , astfel încât

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

Algoritmul validează deoarece gcd este singurul număr care satisface ecuația și împarte numerele de intrare. Algoritmul face, de asemenea, posibilă calcularea coeficientilor a și b prin cel mai mare divizor comun al acestora, aproape fără costuri suplimentare.

Algoritmul Euclidian Extins se referă, de asemenea, la un algoritm foarte similar pentru calcularea celui mai mare divizor comun al polinoamelor și calcularea coeficienților raportului Bezout a două polinoame într-o variabilă.

Algoritmul Euclid extins este util în special atunci când a și b sunt coprime . În aceste condiții, x este reciproca modulo a unui modulo b și y este reciproca modulului a lui b modulo a . În mod similar, algoritmul extins al lui Euclid pentru polinoame permite calcularea reciprocei în extensii algebrice și, în special, în câmpuri finite de ordin nesimplu. Prin urmare, ambii algoritmi extinși Euclid sunt utilizați pe scară largă în criptografie . În special, calcularea modulo invers este un pas esențial în derivarea unei perechi de chei în metoda de criptare a cheii publice RSA .

Descriere

Algoritmul Euclid standard este realizat prin împărțiri succesive cu un rest , în timp ce coeficientul nu este utilizat, doar restul este păstrat. Algoritmul extins folosește și coeficienti de diviziune. Mai precis, algoritmul euclidian standard pentru numerele a și b ca intrare constă în calcularea unei secvențe de coeficienti și a unei secvențe de resturi astfel încât $q_{1},\ldots,q_{k)$ $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{(aceasta definește }}q_ {i})\\&\,\,\,\vdots \end{aligned}}

Principala proprietate a împărțirii cu rest este că inegalitatea din dreapta determină unicitatea ambelor pentru și $q_{i}$ $r_{i+1}$ $r_{i-1}$ $r_{i}.$

Calculul se oprește când ajungem la zero rest . Cel mai mare divizor comun este atunci egal cu ultimul rest diferit de zero $r_{k+1}$ $r_{k}.$

Algoritmul extins al lui Euclid funcționează în mod similar, dar adaugă alte două secvențe

{\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{ și }}0&\leqslant r_{i+1}<|r_{i}|&{\text{(aceasta definește }}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{aliniat}}

De asemenea, calculul se oprește când și ca rezultat obținem $r_{k+1}=0$

$r_{k}$ este egal cu cel mai mare divizor comun al valorilor de intrare și $a=r_{0}$ $b=r_{1}.$
Coeficienții Bezout sunt egali cu și , adică $s_{k)$ $t_{k},$ ${\text{gcd}}(a,b)=r_{k}=as_{k}+bt_{k}$
Coeficientii împărțirii a și b la cel mai mare divizor comun al lor sunt dați de și $s_{k+1}=\pm {\frac {b}({\text{gcd}}(a,b)))$ $t_{k+1}=\pm {\frac {a}({\text{gcd}}(a,b)))$

În plus, dacă ambele numere a și b sunt pozitive și , atunci ${\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

pentru , unde înseamnă partea întreagă a numărului x , adică cel mai mare număr întreg care nu depășește x . $0\leqslant i\leqslant k,$ $\lfloor x\rfloor$

Rezultă că perechea de coeficienți Bezout dată de algoritmul Euclid extins este perechea minimă de coeficienți Bezout, deoarece este singura pereche care satisface ambele inegalități de mai sus.

De asemenea, rezultă că algoritmul poate fi executat fără riscul depășirii întregului de către un program care utilizează numere întregi de dimensiune fixă care este mai mare decât a și b .

Exemplu

Următorul tabel arată cum funcționează algoritmul Euclid extins cu numerele de intrare 240 și 46 . Cel mai mare divizor comun este ultimul element diferit de zero, 2 în coloana de rest. Calculul se termină pe linia 6 deoarece restul este 0 . Coeficienții Bezout apar în ultimele două celule ale penultimului rând. Este ușor de verificat că −9 × 240 + 47 × 46 = 2 . În cele din urmă, ultimele două valori 23 și −120 ale ultimului rând, până la un semn, sunt coeficientii valorilor de intrare 46 și 240 împărțite la cel mai mare divizor comun 2 .

indicele i	coeficientul q i −1	restul r i	s i	t i
0		240	unu	0
unu		46	0	unu
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
patru	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

Dovada

Deoarece secvența este o succesiune descrescătoare de numere întregi nenegative (începând de la i = 2). Apoi algoritmul trebuie să se oprească la un moment dat , ceea ce demonstrează că algoritmul se va termina în cele din urmă. $0\leqslant r_{i+1}<|r_{i}|,$ $r_{i)$ $r_{k+1}=0.$

Deoarece cel mai mare divizor comun va fi același pentru și Acest lucru arată că cel mai mare divizor comun al intrărilor va fi același ca pentru Aceasta demonstrează că este cel mai mare divizor comun al lui a și b . (Până în acest punct, demonstrația este aceeași ca și pentru algoritmul Euclid clasic.) $r_{i+1}=r_{i-1}-r_{i}q_{i},$ $(r_{i-1},r_{i})$ $(r_{i},r_{i+1}).$ $a=r_{0},b=r_{1)$ $r_{k},r_{k+1}=0.$ $r_{k)$

Deoarece și , avem pentru i = 0 și 1. Relația se dovedește prin inducție pentru toate : $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}=(ca_{i-1}+bt_{i-1})-(ca_{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}.

Atunci și sunt coeficienții Bezout. $s_{k)$ $t_k$

Luați în considerare matricea

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

Relațiile recurente pot fi rescrise sub formă de matrice

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

Matricea este matricea identității, iar determinantul ei este unul. Determinantul matricei celei mai din dreapta aici este −1. Rezultă că determinantul este În special, deoarece avem Dacă considerăm aceasta ca o relație Bézout, obținem că și suntem coprim . Relația de mai sus și lema lui Euclid arată că b împarte , adică pentru un întreg d . Împărțind cu raportul , obținem că . Astfel, și sunt numere întregi coprime care sunt câte de împărțire a a și b la un divizor comun, care este cel mai mare divizor comun al lor sau opusul său . $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}$

Pentru a demonstra ultima afirmație, să presupunem că a și b sunt pozitive și . Atunci , și dacă , se poate observa că secvențele s și t pentru ( a , b ) din algoritmul extins sunt, până la zero și unu, secvențele t și s pentru ( b , a ). Definițiile arată apoi că cazul ( a , b ) se reduce la cazul ( b , a ). Astfel, fără pierderea generalității, putem presupune că . ${\text{gcd}}(a,b)\neq \min(a,b)$ $a\neq b$ $a<b$ $a>b$

Puteți vedea că este egal cu 1 și (care există datorită ) este negativ. Astfel, se schimbă semnul și crește strict în valoare absolută, ceea ce urmează prin inducție din definiție și faptul că pentru . Cazul pentru este satisfăcut deoarece . Același lucru este valabil și după primii termeni din aceleași motive. În plus, este ușor de observat că (dacă a și b sunt pozitive și ). Apoi $s_{2}$ $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}|.

Aceasta, împreună cu faptul că nu este mai mică în valoare absolută decât oricare precedentă sau respectiv, completează proba. $s_{k},t_{k)$ $si}$ $t_{i}$

O extensie a algoritmului lui Euclid pentru polinoame

Pentru polinoamele dintr-o variabilă cu coeficienți într- un câmp, totul funcționează într-un mod similar, inclusiv diviziunea lui Euclid, relația lui Bezout și algoritmul extins al lui Euclid. Prima diferență este că în diviziunea euclidiană și în algoritm, inegalitatea ar trebui înlocuită cu inegalitatea de grade. Restul rămâne același, doar înlocuiți numerele întregi cu polinoame. $0\leqslant r_{i+1}<|r_{i}|$ $\deg r_{i+1}<\deg r_{i}.$

A doua diferență constă în limitele mărimii coeficienților Bézout dat de algoritmul Euclid extins, care sunt mai precise în cazul polinoamelor, ceea ce duce la următoarea teoremă.

Dacă a și b sunt două polinoame diferite de zero, algoritmul euclidian extins dă o pereche unică de polinoame ( s , t ) astfel încât

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

și

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

A treia diferență este că pentru polinoame cel mai mare divizor comun este definit până la înmulțire cu o constantă diferită de zero. Există mai multe moduri de a determina cel mai mare divizor comun în mod unic.

În matematică, de obicei este necesar ca cel mai mare divizor comun să fie un polinom redus . Pentru a realiza acest lucru, este suficient să împărțiți toate elementele rezultatului la factorul conducător . Acest lucru permite, dacă a și b sunt coprime, să obțineți 1 în partea dreaptă a inegalității lui Bezout. În caz contrar, obținem o constantă diferită de zero. În algebra computerizată, polinoamele au de obicei coeficienți întregi, iar acest mod de normalizare a celui mai mare divizor comun are ca rezultat un număr mare de fracții. $r_{k}.$

O altă modalitate de a normaliza cel mai mare divizor comun pentru cazul coeficienților întregi este de a împărți polinomul de ieșire la mcd-ul coeficienților polinomului pentru a obține un cel mai mare divizor comun primitiv . Dacă polinoamele de intrare sunt între prime, normalizarea dă cel mai mare divizor comun de 1. Dezavantajul acestei abordări este numărul mare de fracții care trebuie calculate și simplificate. $r_{k},$

A treia abordare este de a extinde algoritmul pentru calcularea secvențelor intermediare de pseudoreziduale ( subrezultate ) similar cu extinderea algoritmului euclidian la algoritmul Euclid extins. Aceasta permite, începând cu un polinom cu coeficienți întregi, să se obțină polinoame cu coeficienți întregi în procesul de calcule. Mai mult, fiecare rest calculat rămâne un subrezultat. În special, dacă polinoamele sunt coprime, atunci relația Bézout se transformă în $r_{i}$

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

unde înseamnă rezultanta pentru a și b . În această formă, relația Bezout nu are un numitor în formulă. Dacă împărțim totul la rezultantă, obținem relația clasică Bezout cu un numitor comun explicit pentru numerele raționale care apar. $\operatorname {Res} (a,b)$

Pseudocod

Pentru a implementa algoritmul de mai sus, trebuie remarcat că doar ultimele două valori ale variabilelor indexate sunt necesare la fiecare pas. Astfel, pentru a economisi memorie, fiecare variabilă indexată ar trebui înlocuită cu doar două variabile.

Pentru simplitate, următorul algoritm (și alți algoritmi din acest articol) utilizează atribuiri paralele . În limbajele de programare care nu acceptă această caracteristică, atribuirea paralelă trebuie efectuată folosind o variabilă suplimentară. De exemplu, prima misiune

(vechi_r, r) := (r, vechi_r - coeficient * r)

echivalentă cu

prov := r; r := vechi_r - coeficient × prov; vechi_r := prov;

și în mod similar pentru alte misiuni paralele. Aceasta duce la următorul cod:

funcția extended_gcd(a, b) (vechi_r, r) := (a, b) (vechi_s, s) := (1, 0) (vechi_t, t) := (0, 1) în timp ce r ≠ 0 do quotient := old_r div r (vechi_r, r) := (r, vechi_r − coeficient × r) (vechi_s, s) := (s, vechi_s − coeficient × s) (vechi_t, t) := (t, vechi_t − coeficient × t) ieșire „Coeficienți Bezout:”, (old_s, old_t) scoatere „ cel mai mare divizor comun:”, old_r scoatere „ coeficienți după mcd:”, (t, s)

Coeficientii împărțirii a și b la cel mai mare divizor comun al lor, care se află și în rezultat, pot avea semnul greșit. Acest lucru este ușor de remediat la sfârșitul calculului, dar nu este făcut aici pentru a simplifica codul. În mod similar, dacă a sau b este zero și al doilea număr este negativ, cel mai mare divizor comun din ieșire este negativ, deci toate semnele din ieșire trebuie inversate.

În cele din urmă, observăm că relația Bezout poate fi rezolvată relativ pentru data . Apoi, o optimizare pentru algoritmul de mai sus ar calcula doar secvența (care duce la coeficientul Bézout ) și ar calcula valoarea la sfârșitul algoritmului: $ax+by={\text{gcd}}(a,b)$ $y$ $a,b,x,{\text{gcd}}(a,b)$ $s_{k)$ $X$ $y$

funcția extended_gcd(a, b) s := 0; vechi_s := 1 r := b; vechi_r := a în timp ce r ≠ 0 do quotient := old_r div r (vechi_r, r) := (r, vechi_r − coeficient × r) (vechi_s, s) := (s, vechi_s − coeficient × s) dacă b ≠ 0 atunci bezout_t := (old_r − old_s × a) div b altfel bezout_t := 0 scoateți „coeficienți bezout :”, (old_s, bezout_t) scoateți „ cel mai mare divizor comun:”, old_r

Cu toate acestea, în multe cazuri aceasta nu va fi o optimizare reală - fostul algoritm este insensibil la depășire atunci când se utilizează numere întregi în mașină (adică numere întregi cu o limită superioară fixă pe reprezentare), înmulțirea old_s * a când se calculează bezout_t poate provoca o depășire . , care limitează optimizarea doar la datele de intrare care nu depășesc jumătate din dimensiunea maximă a numerelor întregi. Dacă se folosesc numere întregi de mărime nelimitată, timpul necesar înmulțirii și împărțirii crește pătratic cu dimensiunea numerelor întregi. Rezultă de aici că „optimizarea” înlocuiește o succesiune de înmulțiri/împărțiri de numere mici cu o singură înmulțire/împărțire, care necesită mai mult timp de execuție decât operațiunile pe care le înlocuiește luate împreună.

Simplificarea diviziunii

DiviziaAbeste în formă canonică simplificată dacă a și b sunt între prime și b este pozitiv. Această formă canonică simplificată poate fi obținută prin înlocuirea celor trei linii de ieșire cu pseudo-cod

dacă s = 0 atunci iese „Diviziunea la zero” dacă s < 0 atunci s := − s ; t := − t ( pentru a evita divizorii de zero ) dacă s = 1 atunci ieșire - t ( pentru a evita divizorii lui 1) ieșire -t_ _s

Dovada acestui algoritm se bazează pe faptul că s și t sunt două numere întregi între prime astfel încât , și apoi . Pentru a obține o formă simplificată canonic, este suficient să schimbați semnul pentru a obține un divizor pozitiv. $ca+bt=0$ ${\frac {a}{b}}=-{\frac {t}{s}}$

Dacă b împarte a uniform, algoritmul efectuează o singură iterație și avem s = 1 la sfârșitul algoritmului. Acesta este singurul caz în care rezultatul este un număr întreg.

Calculul inversului în structuri modulare

Algoritmul Euclid extins este un mijloc important de calculare a reciprocelor în structuri modulare, de obicei numere întregi modulare și extensii de câmp algebric . Un exemplu important al acestui din urmă caz sunt câmpurile finite de ordin nesimplu.

Întregi modulo

Dacă n este un număr întreg pozitiv, inelul Z / n Z poate fi identificat cu mulțimea {0, 1, ..., n -1} a resturilor de împărțire cu un rest de n , adunarea și înmulțirea iau restul de împărțirea cu n a rezultatelor adunării și înmulțirii numerelor întregi. Un element a Z / n Z are un invers (adică un element inversabil ) dacă este relativ prim cu n . În special, dacă n este prim , a are un invers dacă este diferit de zero (modulo n ). Adică, Z / n Z este un câmp dacă și numai dacă n este prim.

Relația lui Bezout afirmă că a și n sunt între prime dacă și numai dacă există numere întregi s și t astfel încât

ns+at=1

Comparația modulo n dă

la\equiv 1\mod n.

Atunci t , sau mai precis, restul împărțirii t la n , este egal cu reciproca a modulo n .

Pentru a adapta algoritmul Euclid extins la această problemă, trebuie remarcat că nu este necesar coeficientul Bezout al lui n și, prin urmare, nu este nevoie să-l calculăm. De asemenea, pentru a obține rezultatul ca număr pozitiv mai mic decât n , puteți folosi faptul că întregul t furnizat de algoritm satisface relația . Adică, dacă , puteți adăuga n la sfârșit. Rezultă un pseudocod în care valoarea de intrare n este un număr întreg mai mare decât 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

Extensii de câmp algebric

Algoritmul Euclid extins este, de asemenea, principalul instrument pentru calcularea inverselor extensiilor de câmp algebric . Un caz important, utilizat pe scară largă în criptografie și teoria codificării , este cazul câmpurilor finite de ordine non-simplu. De fapt, dacă p este simplu și q = p d , câmpul de ordin q este o extensie algebrică a câmpului prim cu p elemente formate din rădăcina unui polinom ireductibil de gradul d .

Extensia algebrică L a câmpului K generată de rădăcina unui polinom ireductibil p de gradul d poate fi identificată cu inelul coeficient , iar elementele sale sunt în relație bijectivă cu polinoame de grad mai mic decât d . Adunarea în L este adunarea. de polinoame. Înmulțirea în L este restul împărțirii cu rest prin p a produsului polinoamelor. Astfel, pentru a completa aritmetica în L , rămâne doar să se determine modul de calcul al elementelor inverse. Acest lucru se face cu algoritmul Euclid extins. $K[X]/\langle p\rangle ,$

Algoritmul este foarte asemănător cu cel de mai sus pentru calcularea inversului modular. Există două diferențe principale - în primul rând, penultima linie nu este necesară, deoarece coeficienții Bezout rezultați au întotdeauna un grad mai mic decât d . În al doilea rând, Cel mai mare divizor comun care rezultă dacă intrările sunt polinoame între prime poate fi orice element diferit de zero al lui K . Acest coeficient Bézout (un polinom are de obicei un grad pozitiv) ar trebui înmulțit cu reciproca acestui element în K . În pseudocodul (mai jos), p este un polinom de grad mai mare decât unu, iar a este un 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 Exemplu

De exemplu, lăsați polinomul să definească câmpul final și să fie elementul a cărui inversă trebuie găsită. Apoi, funcționarea algoritmului este prezentată în tabelul de mai jos. Reamintim că într-un câmp de ordin , avem - z = z și z + z = 0 pentru oricare sau element z al câmpului). Deoarece 1 este singurul element diferit de zero al GF(2), nu este nevoie să ajustați ultima linie a pseudocodului. $p=x^{8}+x^{4}+x^{3}+x+1$ $GF(2^{8})$ $a=x^{6}+x^{4}+x+1$ $2^{n}$

Etapa	privat	r, mai nou	s, știri	t, triton
		$p=x^{8}+x^{4}+x^{3}+x+1$	unu	0
		$a=x^{6}+x^{4}+x+1$	0	unu
unu	$x^{2}+1$	$x^{2}=pa(x^{2}+1)$	unu	$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)$
patru	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)$

Astfel, elementul invers este , ceea ce se confirmă prin înmulțirea celor două elemente și luând restul peste p din rezultat. $x^{7}+x^{6}+x^{3}+x$

Cazul a mai mult de două numere

Puteți gestiona cazul a mai mult de două numere în mod iterativ. Mai întâi să arătăm asta . Pentru dovadă, să punem . Prin definiție, mcd este un divizor al lui și . Apoi pentru unii . În mod similar , este un divizor , deci pentru unii . Lasă . Prin construcție , , dar deoarece este cel mai mare divizor, este un element inversabil al . Și din moment ce , rezultatul este dovedit. ${\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)$

Astfel, dacă , adică și , astfel încât , astfel încât ecuația finală va fi $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).\,

Pentru a merge la n numere, folosim inducția

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

Vezi și

Note

Literatură

Donald Knuth. Capitolul 4 // Arta programarii computerelor . — Addison-Wesley. - T. 2. .
- Tradus de Donald Knuth. Arta de a programa. - 1998. - V. 2. Algoritmi obţinuţi.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . secțiunea 31.2: Cel mai mare divizor comun. // Introducere în algoritmi . - A doua editie. - MIT Press și McGraw-Hill, 2001. - P. 859-861. — ISBN 0-262-03293-7 .
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: Construcție și analiză , ediția a treia = Introducere în algoritmi, ediția a treia. - M. : „Williams” , 2013. - 1328 p. - ISBN 978-5-8459-1794-2 .

Link -uri

Sursa pentru forma algoritmului utilizat pentru a determina inversul multiplicativ în GF(2^8)

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin