Kalkulator rozszerzonego algorytmu Euklidesa

Kalkulator Rozszerzonego Algorytmu Euklidesa oblicza Największy Wspólny Dzielnik (NWD) dwóch liczb całkowitych i znajduje współczynniki Bézouta — liczby całkowite s i t spełniające równanie nwd(a, b) = s·a + t·b. Oprócz obliczania NWD, narzędzie to zapewnia w pełni animowaną tabelę dzieleń krok po kroku, metodę podstawiania wstecznego oraz obliczanie odwrotności modularnej, co czyni je idealnym do nauki teorii liczb, kryptografii i programowania konkurencyjnego.

Co to jest rozszerzony algorytm Euklidesa?

Rozszerzony algorytm Euklidesa (EEA) to rozszerzenie klasycznego algorytmu Euklidesa do wyznaczania NWD. Podczas gdy podstawowy algorytm znajduje nwd(a, b) poprzez kolejne dzielenia, wersja rozszerzona jednocześnie śledzi dwa ciągi liczb całkowitych, które rejestrują, w jaki sposób każda reszta może być wyrażona jako liniowa kombinacja oryginalnych danych wejściowych.

Jak działa ten algorytm

EEA utrzymuje trzy pary wartości — (r, s, t) — na każdym etapie dzielenia:

1. Inicjalizacja: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Każdy krok: oblicz iloraz q = ⌊rₙ₋₁ / rₙ⌋, następnie zaktualizuj rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Zatrzymaj się, gdy reszta = 0; poprzednia reszta to nwd(a, b)
4. Odpowiadające wartości s i t to współczynniki Bézouta

Przykład krok po kroku: nwd(252, 105)

Wynik: nwd(252, 105) = 21, z tożsamością Bézouta: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). Wypróbuj sam powyższy kalkulator, aby uzyskać dokładne współczynniki.

Zastosowania rozszerzonego algorytmu Euklidesa

1. Odwrotność modularna (Kryptografia)

Najważniejszym zastosowaniem jest obliczanie odwrotności modularnych. Jeśli nwd(a, m) = 1, to współczynnik Bézouta s spełnia zależność:

Odwrotności modularne są niezbędne w szyfrowaniu RSA (obliczanie wykładnika klucza prywatnego d), wymianie kluczy Diffie-Hellman oraz kryptografii krzywych eliptycznych.

2. Rozwiązywanie liniowych równań diofantycznych

Równanie ax + by = c ma rozwiązania całkowite wtedy i tylko wtedy, gdy nwd(a, b) dzieli c. Jeśli tak, rozwiązaniem szczególnym jest x₀ = s·(c/d), y₀ = t·(c/d), gdzie d = nwd(a, b), a s, t to współczynniki Bézouta.

3. Chińskie twierdzenie o resztach

EEA jest używany w dowodzie konstrukcyjnym i obliczeniach chińskiego twierdzenia o resztach — znajdowaniu x takiego, że x ≡ a₁ (mod m₁) i x ≡ a₂ (mod m₂) — poprzez obliczanie odwrotności modularnych modułów.

4. Skracanie ułamków i NWW

nwd(a, b) = 1 potwierdza, że ułamek a/b jest nieskracalny. Najmniejsza Wspólna Wielokrotność to nww(a, b) = |a·b| / nwd(a, b).

Współczynniki Bézouta nie są unikalne

Współczynniki Bézouta s i t nie są jedyne. Jeśli (s, t) jest jednym rozwiązaniem, to (s + k·(b/d), t − k·(a/d)) również jest rozwiązaniem dla dowolnej liczby całkowitej k, gdzie d = nwd(a, b). EEA zwraca rozwiązanie, w którym |s| ≤ |b/d| i |t| ≤ |a/d|.

Złożoność czasowa

Rozszerzony algorytm Euklidesa działa w O(log min(a, b)) iteracjach — tyle samo, co podstawowy algorytm Euklidesa. Zgodnie z twierdzeniem Lamégo, liczba kroków nigdy nie przekracza 5-krotności liczby cyfr dziesiętnych mniejszej z liczb wejściowych. Dzięki temu jest niezwykle wydajny nawet dla dużych liczb całkowitych stosowanych w kryptografii.

Często zadawane pytania

Co to jest rozszerzony algorytm Euklidesa?

Rozszerzony algorytm Euklidesa rozszerza algorytm NWD Euklidesa o obliczanie współczynników Bézouta s i t spełniających równanie nwd(a, b) = s·a + t·b. Śledzi on, jak każda reszta może być wyrażona jako liniowa kombinacja a i b w procesie dzielenia.

Co to są współczynniki Bézouta?

Współczynniki Bézouta to liczby całkowite s i t, których istnienie gwarantuje tożsamość Bézouta (twierdzenie w teorii liczb). Spełniają one zależność nwd(a, b) = s·a + t·b i są efektywnie obliczane przez rozszerzony algorytm Euklidesa. Są używane w obliczaniu odwrotności modularnej, rozwiązywaniu równań diofantycznych i chińskim twierdzeniu o resztach.

Jak znaleźć odwrotność modularną za pomocą rozszerzonego algorytmu Euklidesa?

Jeśli nwd(a, b) = 1 (a i b są względnie pierwsze), współczynnik Bézouta s spełnia s·a ≡ 1 (mod b). Odwrotność modularna a mod b to s mod b (skorygowana do wartości dodatniej). Ten kalkulator wyświetla to bezpośrednio w wynikach.

Kiedy odwrotność modularna nie istnieje?

Odwrotność modularna a modulo m istnieje wtedy i tylko wtedy, gdy nwd(a, m) = 1. Jeśli nwd(a, m) > 1, żadna liczba całkowita x nie spełnia równania a·x ≡ 1 (mod m).

Jaka jest złożoność czasowa rozszerzonego algorytmu Euklidesa?

O(log min(a, b)) dzieleń, podobnie jak w przypadku podstawowego algorytmu Euklidesa. Dzięki twierdzeniu Lamégo wiemy, że liczba kroków jest ograniczona przez 5-krotność liczby cyfr dziesiętnych mniejszej liczby, co czyni go bardzo wydajnym.

Dodatkowe zasoby

• Rozszerzony algorytm Euklidesa - Wikipedia
• Tożsamość Bézouta - Wikipedia
• Odwrotność modularna - Wikipedia