Jak obliczyć odwrotność modularną?

Najbardziej efektywną metodą jest Rozszerzony Algorytm Euklidesa, który znajduje liczby całkowite x i y takie, że ax + my = nwd(a, m). Gdy nwd(a, m) = 1, x jest odwrotnością modularną. Alternatywnie, jeśli m jest liczbą pierwszą, Małe Twierdzenie Fermata daje a⁻¹ ≡ a^(m-2) (mod m).

Kiedy odwrotność modularna NIE istnieje?

Odwrotność modularna a (mod m) nie istnieje, gdy nwd(a, m) > 1. Na przykład odwrotność 6 (mod 9) nie istnieje, ponieważ nwd(6, 9) = 3 ≠ 1.

Jakie są praktyczne zastosowania odwrotności modularnej?

Odwrotność modularna ma fundamentalne znaczenie w szyfrowaniu RSA, wymianie kluczy Diffie-Hellman, kryptografii krzywych eliptycznych, rozwiązywaniu kongruencji liniowych, obliczeniach Chińskiego Twierdzenia o Resztach oraz obliczaniu ułamków modularnych.

Kalkulator modularnej odwrotności multiplikatywnej

Q: Co to jest modularna odwrotność multiplikatywna?

Modularna odwrotność multiplikatywna liczby całkowitej a modulo m to liczba całkowita x taka, że a·x ≡ 1 (mod m). Oznacza się ją jako a⁻¹ (mod m) i istnieje wtedy i tylko wtedy, gdy nwd(a, m) = 1 (a i m są względnie pierwsze).

Oblicz modularną odwrotność multiplikatywną liczby całkowitej a względem modula m, używając rozszerzonego algorytmu Euklidesa, wraz z tabelą krok po kroku, weryfikacją i wizualizacją zegarową.

Embed Kalkulator modularnej odwrotności multiplikatywnej Widget

O Kalkulator modularnej odwrotności multiplikatywnej

Co to jest modularna odwrotność multiplikatywna?

Modularna odwrotność multiplikatywna liczby całkowitej a względem modułu m to liczba całkowita x z zakresu [0, m-1] taka, że:

\( a \cdot x \equiv 1 \pmod{m} \)

Zapisuje się ją jako a⁻¹ (mod m). Jest ona analogiczna do odwrotności multiplikatywnej w zwykłej arytmetyce (tj. 1/a), ale w świecie arytmetyki modularnej.

Kluczowy warunek: Odwrotność istnieje wtedy i tylko wtedy, gdy nwd(a, m) = 1 — to znaczy, że a i m muszą być względnie pierwsze.

Jak to się oblicza: Rozszerzony Algorytm Euklidesa

Najbardziej wydajna metoda wykorzystuje Rozszerzony Algorytm Euklidesa. Znajduje on liczby całkowite x i y spełniające tożsamość Bézouta:

\( a \cdot x + m \cdot y = \gcd(a, m) = 1 \)

Gdy nwd(a, m) = 1, biorąc obie strony mod m otrzymujemy a·x ≡ 1 (mod m), więc x jest odwrotnością modularną.

Przykład: Znajdź 3⁻¹ (mod 7):

Rozszerzony algorytm NWD daje: 3·(5) + 7·(-2) = 15 − 14 = 1, zatem 3⁻¹ ≡ 5 (mod 7). Weryfikacja: 3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

Zastosowania w kryptografii i matematyce

🔐

Szyfrowanie RSA

Znajdowanie klucza prywatnego d = e⁻¹ (mod φ(n)) z wykładnika publicznego e

📈

Diffie-Hellman

Protokół wymiany kluczy oparty na logarytmach dyskretnych w arytmetyce modularnej

🇮

Szyfr afiniczny

Deszyfrowanie używa a⁻¹ (mod 26) do odwrócenia klucza szyfrującego

🔢

CRT i teoria liczb

Chińskie Twierdzenie o Resztach i rozwiązywanie kongruencji liniowych ax ≡ b (mod m)

👑

Krzywe eliptyczne

Wzory na dodawanie punktów w ECC wymagają odwrotności modularnych do obliczenia nachylenia

📋

Ułamki modularne

Obliczanie a/b (mod m) jako a · b⁻¹ (mod m), gdy nwd(b, m) = 1

Często zadawane pytania

P: Dlaczego odwrotność nie zawsze istnieje?

Ponieważ arytmetyka modularna "zapętla się", niektóre wielokrotności liczby a mogą nigdy nie trafić na 1 mod m. Dzieje się tak dokładnie wtedy, gdy a i m mają wspólny dzielnik — tzn. nwd(a, m) > 1.

P: Czy istnieje wzór dla modułu będącego liczbą pierwszą?

Tak! Jeśli m jest liczbą pierwszą, a liczba a nie jest wielokrotnością m, Małe Twierdzenie Fermata daje: a⁻¹ ≡ a^m-2 (mod m). Jest to często stosowane w programowaniu konkurencyjnym.

P: Czy wynik jest unikalny?

Tak, wynik jest unikalny modulo m. Zawsze podajemy wynik kanoniczny w zakresie [0, m-1]. Inne poprawne odwrotności to x + km dla dowolnej liczby całkowitej k, ale wszystkie są równoważne mod m.

P: Co jeśli liczba a jest ujemna?

Algorytm obsługuje liczby ujemne. Wewnętrznie najpierw obliczamy a (mod m), aby uzyskać nieujemnego reprezentanta, a następnie znajdujemy jego odwrotność. Wynik jest zawsze w zakresie [0, m-1].

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Kalkulator modularnej odwrotności multiplikatywnej" na https://MiniWebtool.com/pl// z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Zaktualizowano: 18 lutego 2026 r.

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.

Kalkulator modularnej odwrotności multiplikatywnej

Blokada reklam uniemożliwia wyświetlanie reklam

O Kalkulator modularnej odwrotności multiplikatywnej

Co to jest modularna odwrotność multiplikatywna?

Jak to się oblicza: Rozszerzony Algorytm Euklidesa

Zastosowania w kryptografii i matematyce

Często zadawane pytania

Polecane narzędzia: