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:

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. }

• Kod źródłowy NWD
• Kod źródłowy Współczynniki p i q

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

• Kod źródłowy Zadanie 1