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:

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:

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

Często zadawane pytania