Strona główna » Algorytmy » Artykuły » Rozszerzony Algorytm Euklidesa
 

Rozszerzony Algorytm Euklidesa

Wstęp

Rozszerzony algorytm Euklidesa wyznacza współczynniki kombinacji dwóch liczb, która w sumie daje ich największych wspólny dzielnik. Tego typu algorytm wykorzystuje się w kryptografii zarówno do szyfrowania jak również łamania szyfrów. Przykładowo został on wykorzystany w szyfrze Afinicznym w celu jak najszybszego znalezienia elementu odwrotnego.

Algorytm

Rozszerzony algorytm Euklidesa pozwala na wyznaczenie współczynników p i q w równaniu NWD(a, b) = a·p + b·q

W celu znalezienia obu współczynników p i q należy upewnić się, że a > b. Jeśli tak nie jest liczby a i b wystarczy zamienić miejscami. Następnie:

  1. zapisz a = k·b + r, gdzie r to reszta z dzielenia a przez b
  2. jeśli b = 0 to współczynnik k jest NWD(a, b)
  3. jeśli b ≠ 0 to wróć do kroku 1 przyjmując, że a' = b i b' = r

Po wypisaniu wszystkich kolejnych równań należy do ostatniego równania podkładać wszystkie poprzednie, nie wymnażać żadnego iloczynu z a i b!. Całe równanie powinno się uprościć do postaci a·p + b·q.

Znaleziona para liczb p i q nie jest jednoznacza!

Przykład

Przypuśćmy, że chcemy wyliczyć NWD(123, 27). Wtedy:

abRównanie
12327123 = 4·27 + 15
271527 = 1·15 + 12
151215 = 1·12 + 3
12312 = 4·3 + 0
30-

Wynikiem NWD(123, 27) = 3. Wyznaczmy teraz współczynniki p i q:

3 = 15 - 1·12 = 15 - 1·(27 - 1·15) = 15 - 27 + 15 = 2·15 - 27 = 2·(123 - 4·27) - 27 = 2·123 - 8·27 - 27 = 2·123 - 9·27

Z tego ostatecznie wynika, że p = 2, a q = -9.

Implementacja

NWD

W celu znalezienia NWD dwóch liczb wystarczy prosta funkcja iteracyjna, która nie wymaga pamiętania wszystkich kroków wykonanych po kolei. Wtedy kod będzie miał następującą postać:

  1. int NWD(int a, int b) {
  2.   if (b > a)
  3.     swap(a, b);
  4.   int t;
  5.   do {
  6.     t = (a - (a / b)*b);
  7.     a = b;
  8.     b = t;
  9.   } while (b != 0);
  10.   return a;
  11. }

(2.) Najpierw należy upewnić się, że a > b. Jeśli tak nie jest to (3.) wartości należy zamienić miejscami. (4.) Następnie deklarujemy tymczasową zmienną t i w pętli (5. - 9.) dopóki b jest różne od 0 wyliczane są kolejne wartości a i b. Na koniec wystarczy (10.) zwrócić wartość zmiennej a.

Należy zauważyć, że tego typu funkcja traci cenne informacje, które możnaby wykorzystać do obliczenia współczynników p i q!

Powyższy kod można przetestować przy pomocy poniższej funkcji main():

  1. int main() {
  2.   int a, b;
  3.   cout << "Podaj liczby a i b" << endl;
  4.   cin >> a >> b;
  5.   int nwd = NWD(a, b);
  6.   cout << "NWD(" << a << ", " << b << ") = " << nwd << endl;
  7.   system("pause");
  8.   return 0;
  9. }

Współczynniki p i q

W celu wyliczenia współczynników p i q trzeba pamiętać wszystkie poprzednie wartości a i b. Tutaj warto zastosować rekurencję tak, aby najpierw dojść do ostatecznego wyniku i podczas powrotu do pierwszego wywołania składać od razu szukane równanie.

W kodzie została wykorzystana funkcjonalność biblioteki utility, która pozwala na tworzeniu par obiektów. Przykładowy kod wygląda następująco:

  1. pair<int, int> rozszerzonyEuklides(int a, int b) {
  2.   if (b > a)
  3.     swap(b, a);
  4.   if (b == 0)
  5.     return make_pair(1, 0);
  6.   pair<int, int> p = rozszerzonyEuklides(b, a - (a / b)*b);
  7.   return make_pair(p.second, p.first - (a / b) * p.second);
  8. }

(2. - 3.) Zawsze należy upewnić się, że a > b. Następnie jeśli (4.) b jest 0 to (5.) należy zwrócić parę liczb (1, 0). Jednak w przypadku normalny: (6.) wywołujemy rekurencyjnie funkcję z nowymi argumentami. Po odczytaniu wyniku można (7.) przejść do wyliczenia następnego i jego zwrócenia.

Funkcję tę można przetestować poniższą funkcją main():

  1. int main() {
  2.   int a, b;
  3.   cout << "Podaj liczby a i b" << endl;
  4.   cin >> a >> b;
  5.   pair<int, int> p = rozszerzonyEuklides(a, b);
  6.   int nwd = p.first*a + p.second*b;
  7.   cout << "NWD(" << a << ", " << b << ") = ";
  8.   cout << p.first << "*" << a << " + ";
  9.   cout << p.second << "*" << b << " = " << nwd << endl;
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Zmodyfikuj funkcję NWD tak, aby wypisywała na ekran kolejne równania, które powstają podczas wykonywania algorytmu. Przykładowo program powinien wypisać na ekran:

  1. 123 = 2*57 + 9
  2. 57 = 6*9 + 3
  3. 9 = 3*3 + 0
  4. NWD(123, 57) = 3