Główna zawartość
Kurs: Informatyka > Rozdział 2
Lekcja 5: Arytmetyka modularna- Co to jest arytmetyka modularna?
- Operator modulo
- Wyzwanie modulo
- Przystawanie modulo
- Relacja przystawania
- Relacje równoważności
- Twierdzenie o reszcie z dzielenia
- Dodawanie i odejmowanie modularne
- Dodawanie modularne
- Wyzwanie modulo (dodawanie i odejmowanie)
- Mnożenie modularne
- Mnożenie modularne
- Potęgowanie modularne
- Szybkie potęgowanie modularne
- Szybkie potęgowanie modularne
- Odwrotność modularna
- Algorytm Euklidesa
© 2024 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Odwrotność modularna
Czym jest odwrotność?
Przypomnijmy, że liczba pomnożona przez swoją odwrotność jest równa 1. Z podstaw arytmetyki wiemy, że:
- Odwrotnością liczby A jest 1/A, ponieważ A * 1/A = 1 (np. odwrotnością 5 jest 1/5)
- Wszystkie liczby rzeczywiste różne od 0 mają liczby odwrotne
- Pomnożenie liczby przez odwrotność A jest równoważne podzieleniu jej przez A (np. 10/5 to to samo, co 10* 1/5)
Czym jest odwrotność modulo?
W arytmetyce modularnej nie mamy operacji dzielenia. Jednak dysponujemy odwrotnością modularną.
- Odwrotnością modularną A (mod C) jest A^-1
- (A * A^-1) ≡ 1 (mod C) ub równoważnie (A * A^-1) mod C = 1
- Tylko liczby względnie pierwsze z C (liczby nie posiadające wspólnych czynników pierwszych z C) posiadają odwrotność modularną (mod C)
Jak znaleźć odwrotność modularną
Metoda naiwna znajdowania odwrotności modularnej do A (mod C) to:
krok 1. Oblicz A * B mod C, dla wartości B od 0 do C-1
krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1
Zauważ, że B mod C może przyjmować wartości całkowite wyłącznie od 0 do C-1, więc testowanie dla większych wartości B jest zbyteczne.
Przykład: A=3, C=7
Krok 1. Obliczmy A * B mod C dla B z przedziału 0 do C-1
3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <--- ZNALEZIONO ODWROTNOŚĆ!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
Krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1
5 jest odwrotnością modularną 3 mod 7 ponieważ 5*3 mod 7 = 1
Proste!
Policzmy jeszcze jeden przykład, w którym nie znajdujemy odwrotności.
Przykład: A=2 C=6
Krok 1. Obliczmy A * B mod C dla B z przedziału 0 do C-1
2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)
Krok 2. Odwrotnością modularną A mod C jest takie B, że A * B mod C = 1
Warunek A * B mod C = 1, nie jest spełniony dla żadnego B. Tak więc, A nie posiada odwrotności modularnej (mod 6).
Dzieje się tak dlatego, że 2 nie jest względnie pierwsze z 6 (mają wspólny czynnik pierwszy 2).
Dzieje się tak dlatego, że 2 nie jest względnie pierwsze z 6 (mają wspólny czynnik pierwszy 2).
Ta metoda wydaje się powolna...
Istnieje dużo szybszy sposób znajdowania odwrotności A (mod C). Przedyskutujemy ją w kolejnych artykułach dotyczących Rozszerzonego Algorytmu Euklidesa.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji