Algorytm Euklidesa jest to algorytm wyznaczania największego wspólnego dzielnika (NWD, ang. Greatest Common Divisor) dwóch liczb całkowitych. Jak nazwa wskazuje, został opracowany przez greckiego matematyka – Euklidesa.
Największy wspólny dzielnik to liczba, która dzieli te liczby bez reszty i jest ona możliwie największa. Można go wykorzystać do skracania ułamków lub wyznaczenia najmniejszej wspólnej wielokrotności (NWW). Rozszerzona wersja używana jest również w kryptografii, w algorytmach takich jak RSA.
Istnieją trzy wersje algorytmu:
- z wykorzystaniem odejmowania (wersja niezoptymalizowana)
- z wykorzystaniem funkcji modulo, czyli reszty z dzielenia (wersja zoptymalizowana)
- roszerzony algorytm Euklidesa
Algorytm Euklidesa z użyciem odejmowania
Algorytm polega na wybieraniu większej z dwóch liczb i zamienieniu jej na różnicę większej i mniejszej. Czynność tą powtarzamy do momentu uzyskania dwóch takich samych wartości, które dają nam NWD.
Nalęży pamiętać, że ta wersja algorytmu jest nieoptymalna i dla odpowiednio dobranej pary liczb, może wymagać bardzo dużej liczby iteracji, aby obliczyć wynik.
def gcd(a, b):
if a > b:
return gcd(a-b, b)
elif a < b:
return gcd(a, b-a)
else:
return a
print(gcd(6, 24))
Algorytm Euklidesa z użyciem modulo
W tej wersji algorytmu w każdej iteracji wykonujemy dwie operacje:
- a = b
- b = a mod b
Działanie przerywamy w momencie znalezienia reszty równej 0.
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(6, 24))
Rozszerzony Algorytm Euklidesa
Rozszerzony algorytm Euklidesa wyznacza współczynniki kombinacji dwóch liczb, która w sumie daje ich największych wspólny dzielnik. Ten algorytm wykorzystuje się w kryptografii zarówno do szyfrowania, ale również łamania szyfrów.
Rozszerzony algorytm Euklidesa pozwala na wyznaczenie współczynników x i y w równaniu:
def gcd_extended(a, b):
if a == 0:
return b, 0, 1
gcd, x1, y1 = gcd_extended(b % a, a)
x = y1 - (b//a) * x1
y = x1
return gcd, x, y
print(gcd_extended(6, 24))