Как рассчитать матрицу обратных ключей в алгоритме Hill Cipher?

Question

Мне очень трудно понять, как вычисляется обратная матрица в алгоритме Hill Cipher. Я понимаю, что все это делается по модулю арифметики, но почему-то все не складывается. Буду очень признателен за простое объяснение!

Рассмотрим следующую матрицу ключей Hill Cipher:

 5 8 
17 3

Пожалуйста, используйте вышеуказанную матрицу для иллюстрации.

Answer 1

Вы должны изучить теорему линейной конгруэнции и расширенный алгоритм GCD , которые принадлежат Теории чисел , чтобы понять математику, стоящую за по модулю арифметика .

Например, обратная матрица K является (1 / det (K)) * присоединенной (K), где det (K) <> 0.

Я полагаю, что вы не понимаете, как рассчитать 1 / det (K) в модульной арифметике, и вот здесь начинают играть линейные сравнения и GCD.

Ваш K имеет det (K) = -121. Допустим, по модулю m равно 26. Мы хотим, чтобы x * (- 121) = 1 (mod 26).
[a = b (mod m) означает, что ab = N * м]

Мы можем легко найти, что для x = 3 вышеупомянутое сравнение верно, потому что 26 делит (3 * (- 121) -1) точно. Конечно, правильный способ - использовать GCD в обратном порядке для вычисления x, но у меня нет времени объяснять, как это сделать. Проверьте расширенный алгоритм GCD:)

Теперь inv (K) = 3 * ([3 -8], [-17 5]) (мод 26) = ([9 -24], [-51 15]) (мод 26) = ([9 2], [1 15]) .

Обновление: Извлечение Основы теории вычислительных чисел , чтобы узнать, как вычислять модульные инверсии с помощью расширенного евклидова алгоритма. Обратите внимание, что -121 mod 26 = 9, поэтому для gcd(9, 26) = 1 мы получаем (-1, 3).

Answer 2

По моему очень скромному мнению, гораздо проще вычислить обратную матрицу (модульную или иную) с помощью метода Гаусса-Джордана. Таким образом, вам не нужно вычислять определитель, а метод очень просто масштабируется до сколь угодно больших систем.

Просто посмотрите «Gauss Jordan Matrix Inverse» - но, резюмируя, вы просто присоединяете копию единичной матрицы справа от матрицы, которую нужно инвертировать, а затем используете операции со строками, чтобы уменьшить вашу матрицу до ее решения это единичная матрица. На этом этапе присоединенная единичная матрица стала обратной к исходной матрице. Voila!