Algoritmul lui Euclid extins

În aritmetică și programare , algoritmul extins al lui Euclid este o extensie a algoritmului lui Euclid care calculează nu numai cel mai mare divizor comun (indicat cu GCD mai jos) între două numere întregi a și b , ci și coeficienții identității lui Bézout x și y astfel acea:

$ax+by=\operatorname {MCD} (a,b).$ ${\ displaystyle ax + by = \ operatorname {MCD} (a, b).}$ ${\ displaystyle ax + by = \ operatorname {MCD} (a, b).}$

Algoritmul extins al lui Euclid este deosebit de util atunci când a și b sunt numere întregi coprimă : în acest caz x este inversul multiplicativ al unui modul b și y este inversul multiplicativ al lui b modulo a .

Adesea, expresia algoritmului extins al lui Euclid este indicată și de un alt algoritm, foarte asemănător cu cel anterior, pentru calculul celui mai mare divizor comun dintre polinoame și coeficienții lor de identitate Bézout.

Ambii algoritmi își găsesc aplicația în criptografie , în special calculul inversului multiplicativ modular este un pas fundamental pentru a cripta mesajele cu algoritmul de cheie publică RSA .

Prima documentare despre algoritm datează din secolele V - VI î.Hr. , de către matematicianul indian Aryabhata . Apoi a fost redescoperit de mai multe ori independent, de exemplu de Bachet francez în 1621 și apoi de Euler în jurul anului 1731 ^[1] .

Exemplu

Tabelul următor arată cu un exemplu cum se desfășoară algoritmul extins al lui Euclid în cazul numerelor 20 și 7.

Calculul continuă cu o serie de iterații i de la 0 la n . Se oprește atunci când rezultatul din coloana „rest” este nul (în linia 4 din exemplu), deci cel mai mare divizor comun este 1 și, prin urmare, 20 și 7 sunt coprimi.

Coeficienții Bézout sunt rezultatele din ultimele două coloane ale penultimului rând. De fapt, este ușor să verificați identitatea:

$ax+by=\operatorname {MCD} (a,b)$ ${\ displaystyle ax + by = \ operatorname {MCD} (a, b)}$ ${\ displaystyle ax + by = \ operatorname {MCD} (a, b)}$ devine $20\times (-1)+7\times 3=1$ ${\ displaystyle 20 \ times (-1) +7 \ times 3 = 1}$ ${\ displaystyle 20 \ times (-1) +7 \ times 3 = 1}$

Rezultatele ultimelor două coloane din ultimul rând, 7 și −20, sunt, semnate în afară, coeficienții 7 și 20 în raport cu cel mai mare divizor comun 1.

indexul i	coeficientul q _i _-1	odihna r _i	x _i	y _i
0		20	1	0
1		7	0	1
2	20 ÷ 7 = 2	20 - 2 × 7 = 6	1-2 × 0 = 1	0 - 2 × 1 = −2
3	7 ÷ 6 = 1	7 - 1 × 6 = 1	0 - 1 × 1 = −1	1 - 1 × (−2) = 3
4	6 ÷ 1 = 6	6 - 6 × 1 = 0	1 - 6 × (−1) = 7	−2 - 6 × 3 = −20

Deoarece cele două numere sunt coprimă, avem și:

-1 este inversul multiplicativ al lui 20 modulo 7, adică $20\times (-1)\equiv 1\mod 7$ ${\ displaystyle 20 \ times (-1) \ equiv 1 \ mod 7}$ ${\ displaystyle 20 \ times (-1) \ equiv 1 \ mod 7}$
3 este inversul multiplicativ al lui 7 modulo 20, adică $7\times 3\equiv 1\mod 20$ ${\ displaystyle 7 \ times 3 \ equiv 1 \ mod 20}$ ${\ displaystyle 7 \ times 3 \ equiv 1 \ mod 20}$ .

Notă

^ André Weil, Teoria numerelor , Birkhäuser, 2001, pp. 6-7, 176-77, ISBN 978-0-8176-4571-7 .

Portal de criptografie

Portalul de matematică

[1] André Weil, Teoria numerelor , Birkhäuser, 2001, pp. 6-7, 176-77, ISBN 978-0-8176-4571-7 .

[1]