Trudno mi zrozumieć, w jaki sposób obliczana jest odwrotność macierzy w algorytmie Szyfrowania w poziomie. Wpadłem na pomysł, że wszystko odbywa się w arytmetyce modulo, ale w jakiś sposób rzeczy się nie sumują. Byłbym wdzięczny za proste wyjaśnienie!Jak obliczyć odwrotną macierz klawiszy w algorytmie algorytmu Hill?
Rozważmy następujący Hill Cipher klucza matrycy:
5 8
17 3
Aby skorzystać z powyższej macierzy dla ilustracji.
Musisz uczyć się Linear congruence theorem i extended GCD algorithm, które należą do Number Theory, aby zrozumieć matematykę stojącą za modulo arithmetic.
Odwrotność macierzy K jest na przykład (1/det (K)) * adjoint (K), gdzie det (K) <> 0.
Zakładam, że nie rozumiem, jak obliczyć 1/det(K) w arytmetykach modulo i tutaj, gdzie zaczynają grać liniowe kongruencje i GCD.
Twoje K ma det (K) = -121. Powiedzmy, że modulo m wynosi 26. Chcemy x * (- 121) = 1 (mod 26).
[A = B (mod m) oznacza, że AB = N * m]
Można łatwo zauważyć, że do x = 3 wyżej kongruencji się tak dlatego 26 podziałów (3 * (- 121) - 1) dokładnie. Oczywiście właściwym sposobem jest użycie GCD w odwrotnej kolejności do obliczenia x, ale nie mam czasu na wyjaśnienie, jak to zrobić. Sprawdź rozszerzony algorytm GCD :)
Teraz, inv (K) = 3 * ([3-8], [-17 5]) (mod 26) = ([9 -24], [-51 15 ]) (mod 26) = ([9 2], [1 15]).
Aktualizacja: Wyjazd Basics of Computational Number Theory, aby zobaczyć, jak obliczyć odwrotności modułowe z rozszerzonego algorytmu Euklidesa. Zauważ, że -121 mod 26 = 9, więc dla gcd(9, 26) = 1 otrzymujemy (-1, 3).
Pozdrawiam! :) - –