Principiul Algoritmului:
Algoritmul Euclidian Extins nu numai că calculează cel mai mare divizor comun gcd(a, m) a două numere întregi a și m, dar găsește și numerele întregi x și y astfel încât ax + my = gcd(a, m)。
Aceasta este o aplicație a identității lui Bézout (ecuația lui Bézout).
Pașii Algoritmului:
- Algoritmul Euclidian:Calculați gcd(a, m) folosind algoritmul diviziunii, înregistrând câtul și restul la fiecare pas.
- Substituție Inversă:Începând de la ultimul pas, substituiți înapoi pentru a exprima fiecare rest ca o combinație liniară a și m.
- Rezolvare pentru Coeficienți:În final, obțineți coeficienții x și y care satisfac ax + my = gcd(a, m).
Invers Modular:
Când gcd(a, m) = 1 (adică a și m sunt coprime), există un invers multiplicativ al lui a modulo m, notat ca a-1 mod m. În acest caz, x este inversul modular, satisfăcând a × x ≡ 1 (mod m)。
Dacă x este negativ, trebuie ajustat la o valoare pozitivă: x' = x mod m.
Aplicații:
- Criptografie:Calcularea cheii private în algoritmul RSA necesită găsirea inversului modular.
- Probleme de Teoria Numerelor:Rezolvarea congruențelor liniare de forma ax ≡ b (mod m).
- Combinatorică:Calcul Combinatoric Modular (Teorema lui Lucas, etc.)
- Programare Competitivă:Calcul Rapid al Inversului Modular pentru a Evita Problemele de Precizie din Împărțire
Complexitate Temporală:
O(log min(a, m)), La fel ca Algoritmul Euclidian
Identitatea lui Bézout:
Pentru orice numere întregi a și m, există numere întregi x și y astfel încât ax + my = gcd(a, m). Acești coeficienți x și y pot fi calculați eficient folosind Algoritmul Euclidian Extins.