Rozszerzony algorytm Euklidesa

Rozszerzony algorytm Euklidesa to algorytm używany do znajdowania największego wspólnego dzielnika (NWD) dwóch liczb, a także współczynników $x$ i $y$ w równaniu diofantycznym.

ax+by=NWD(a,b)

Algorytm ten jest rozszerzeniem klasycznego algorytmu Euklidesa, który służy do znajdowania NWD dwóch liczb. Rozszerzony algorytm Euklidesa zwraca również współczynniki, które mogą być używane do rozwiązywania równań modularnych i innych problemów w teorii liczb oraz kryptografii.

Implementacja rozszerzonego algorytmu Euklidesa w programie Python

Poniżej znajduje się implementacja rozszerzonego algorytmu Euklidesa w programie Python.

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

# Przykład użycia
a = 30
b = 20
gcd, x, y = extended_gcd(a, b)
print(f"Największy wspólny dzielnik (NWD) {a} i {b} to {gcd}.")
print(f"Współczynniki: x = {x}, y = {y}, spełniają równanie: {a}*({x}) + {b}*({y}) = {gcd}")

Dla a=30 i b=20, algorytm zwraca NWD 10 oraz współczynniki x=1 i y=−1y=−1, co oznacza, że:
30⋅1+20⋅(−1)=10

Rozszerzony algorytm Euklidesa jest podstawowym narzędziem w wielu zastosowaniach matematycznych i kryptograficznych, takich jak znajdowanie odwrotności modularnej w kryptografii RSA.