Rozszerzony algorytm Euklidesa

Powtórzenie: szyfrowanie z kluczem publicznym - Informatyka - liceum klasa 4, zakres rozszerzony (Python)

Przypomnienie: rozszerzony algorytm Euklidesa oprócz `nwd(a, b)` daje liczby `x`, `y` z `a*x + b*y = nwd(a, b)`. Gdy `nwd(e, m) = 1`, to `x` (wzięte modulo `m`) jest **odwrotnością** `e` modulo `m`: `e * x % m == 1`.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

g, x, y = ext_gcd(17, 3120)
print(g, x, y, 17 * x + 3120 * y)
print("odwrotność 17 modulo 3120:", x % 3120)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 4, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.