Algorytm Euklidesa - znajdowanie największego wspólnego dzielnika

Stronę tą wyświetlono już: 175 razy

Algorytm Euklidesa stanowi wstęp do utworzenia jego rozszerzonej wersji ważnej przy szyfrowaniu danych szyfrem RSA z kluczem prywatnym i publicznym. Podstawowy model tego algorytmu operuje na różnicach dwóch liczb całkowitych a i b tak długo, aż te liczby osiągną taką samą wartość. Ważne jest aby odejmować od największej mniejszą liczbę.

O wiele lepszym i efektywniejszym rozwiązaniem jest użycie algorytmu wykorzystującego reszty z dzielenia liczb a i b. Po każdym kroku liczba a przyjmuje wartość dzielnika, czyli liczby b, która w kolejnych krokach przyjmuje wartość a % b (czyli reszty z dzielenia a przez b). Oto przykładowy kod napisany w Pythonie pokazujący obie te metody wyznaczania największego wspólnego dzielnika dwóch liczb a i b:

Listing 1
  1. #!/usr/bin/env python
  2. def NWD(a, b):
  3. c = 0
  4. while b != 0:
  5. c = a % b
  6. print("a = {a}; b = {b}".format(a = a, b = b))
  7. a, b = b, c
  8. print("a = {a}; b = {b}".format(a = a, b = b))
  9. return a
  10. def classicNWD(a, b):
  11. while a != b:
  12. a, b = max(a, b), min(a, b)
  13. print("a = {a}; b = {b}".format(a = a, b = b))
  14. a = a - b
  15. print("a = {a}; b = {b}".format(a = a, b = b))
  16. return a
  17. def main(args):
  18. a = int(input("Podaj pierwszą liczbę całkowitą dodatnią: "))
  19. b = int(input("Podaj drugą liczbę całkowitą dodatnią: "))
  20. print("Metoda z wydajniejsza: n")
  21. print("nNajwiększy wspólny dzielnik liczb {a} i {b} jest równy: {NWD}".format(a = a, b = b, NWD = NWD(a, b)))
  22. print("nObliczanie NWD metodą klasyczną:n")
  23. print("nNajwiększy wspólny dzielnik liczb {a} i {b} jest równy: {NWD}".format(a = a, b = b, NWD = classicNWD(a, b)))
  24. return 0
  25. if __name__ == '__main__':
  26. import sys
  27. sys.exit(main(sys.argv))

Przykład działania powyższego programu dla liczb a = 121 i b = 21:

Podaj pierwszą liczbę całkowitą dodatnią: 121
Podaj drugą liczbę całkowitą dodatnią: 21
Metoda z wydajniejsza:

a = 121; b = 21
a = 21; b = 16
a = 16; b = 5
a = 5; b = 1
a = 1; b = 0

Największy wspólny dzielnik liczb 121 i 21 jest równy: 1

Obliczanie NWD metodą klasyczną:

a = 121; b = 21
a = 100; b = 21
a = 79; b = 21
a = 58; b = 21
a = 37; b = 21
a = 21; b = 16
a = 16; b = 5
a = 11; b = 5
a = 6; b = 5
a = 5; b = 1
a = 4; b = 1
a = 3; b = 1
a = 2; b = 1
a = 1; b = 1

Największy wspólny dzielnik liczb 121 i 21 jest równy: 1
Aby kontynuować, naciśnij dowolny klawisz . . .

Jak widać liczba operacji koniecznych do wyznaczenia wspólnego dzielnika liczb a i b w przypadku klasycznego algorytmu Euklidesa wymaga wykonania znacznie większej liczby operacji niż w przypadku algorytmu wykorzystującego resztę z dzielenia.

Komentarze