50574 afișări Candale Silviu (silviu) 14.01.2020
www.pbinfo.ro
Etichete: nicio etichetă

Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a două numere naturale are următoarea consecință: pentru două numere naturale nenule a, b există numerele întregi x, y astfel încât ax+by=d, unde d=(a,b) este cel mai mare divizor comun al lui a și b.

Algoritmul lui Euclid

Algoritmul lui Euclid se bazează pe următoarea formulă:

(a,b)={adacă b=0(b,r)dacă b0, unde r este restul împărțirii lui a la b.

Analizăm cazul b0. Fie d=(a,b) Conform teoremei împărțiri cu rest, există numele naturale c și r, astfel încât a=bc+r, unde 0r<b.

Dacă d|a și d|b atunc d|(abc), adică d|r. Să presupunem că există un număr n>d, astfel încât n=(b,r). Atunci n|b și n|r, deci b|(bc+r), adică n|a. Astfel, n este divizor comun al lui a și b, dar d este cel mai mare divizor comun al lui a și b – contradicție.

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, y de mai sus, vom extinde funcția de mai sus, adăugându-i parametrii de ieșire 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, atunci d = a și deoarece a * 1 + 0 * y = a, deducem că x=1, iar y poate lua orice valoare, de exemplu y=0;
  • dacă b este nenul, se determină în urma autoapelului x1 și y1 astfel încât b*x1+r*y1=d, unde r = a % b. Pe de altă parte, a = b * c + r, unde c = a / b, deci r = 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, unde c = a / b – câtul impărțirii
    • a * y1 + b * (x1 - a / b * y1) = d
    • deci x = y1 și y = 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ă AA11modN. Atunci (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 AX1modN, deoarece NY0modN. De aici rezultă că inversul modular al lui 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 Cnk modulo P, unde P este un număr prim.


50574 afișări Candale Silviu (silviu) 14.01.2020
www.pbinfo.ro
Du-te sus!