Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a două numere naturale are următoarea consecință: pentru două numere naturale nenule
Algoritmul lui Euclid
Algoritmul lui Euclid se bazează pe următoarea formulă:
Analizăm cazul
Dacă
Următoarea funcție recursivă implementează algoritmul lui Euclid și întoarce rezultatul printr-un parametru de ieșire:
void euclid(int a , int b ,int & d) { if(b == 0) d = a; else euclid(b , a % b , d); }
Algoritmul extins
Pentru a determina numere x
și y
:
void euclid(int a , int b ,int & d, int & x ,int & y);
Determinarea valorilor lui x
și y
se va face astfel:
- dacă
b
este nul, atuncid = a
și deoarecea * 1 + 0 * y = a
, deducem căx=1
, iary
poate lua orice valoare, de exempluy=0
; - dacă
b
este nenul, se determină în urma autoapeluluix1
șiy1
astfel încâtb*x1+r*y1=d
, under = a % b
. Pe de altă parte,a = b * c + r
, undec = a / b
, decir = a - b * c
. Înlocuind, obținem:b * x1 + (a - b * c) * y1 = d
b * x1 + a * y1 - b * c * y1 = d
a * y1 + b * (x1 - c * y1) = d
, undec = a / b
– câtul impărțiriia * y1 + b * (x1 - a / b * y1) = d
- deci
x = y1
șiy = x1 - a / b * y1
Funcția următoare implementează algoritmul descris mai sus:
void euclid(int a , int b ,int & d, int & x ,int & y) { if(b == 0) { d = a; x = 1, y = 1; } else { int x1 , y1; euclid(b , a % b , d, x1 , y1); x = y1; y = x1 - a / b * y1; } }
Invers modular
Operația B/A
nu poate fi realizată modulo N
astfel: (B/A) % N != ((A % N)/(B % N)) % N
– ușor de verificat pentru exemple concrete – deși relațiile similare au loc pentru adunare și înmulțire.
Restul împărțirii la N
a lui B/A
poate fi determinat, dacă A
și N
sunt prime între ele, prin intermediul inversului modular – dacă A
și N
nu sunt prime între ele, inversul modular nu există.
Mai precis, dacă 1 ≤ A < N
, inversul lui A
modulo N
este un număr natural 1 ≤ A
-1
< N
cu proprietatea că (B/A) % N = (B * A
-1
) % N = ((B%N)*(A
-1
%N))%N
.
Pentru a determina inversul modular, folosim algoritmul lui Euclid extins. Mai precis, conform algoritmului, există X
și Y
astfel încât A*X + N*Y = 1
, deoarece 1=cmmdc(A,N)
, A
și N
fiind prime între ele. Trecând la operațiile modulo N
, obtinem A
modulo N
este chiar X
. Dacă X
determinat astfel este negativ, îl vom mări cu N
până când devine pozitiv.
Următoarea secvență C++ determină inversul modular al lui A
, modulo N
:
void euclid(int a , int b ,int & x ,int & y) { if(b == 0) { x = 1, y = 1; } else { int x1 , y1; euclid(b , a % b , x1 , y1); x = y1; y = x1 - a / b * y1; } } int main() { int A = 9, N = 11; // prime intre ele, 1 <= A < N int X , Y; euclid(A, N , X ,Y); while(X < 0) X += N; cout << X; // 5 return 0; }
Inversul modular poate fi folosit, de exemplu pentru a calcula P
, unde P
este un număr prim.