如何计算Hill密码算法中的逆键矩阵？ [英] How to calculate the inverse key matrix in Hill Cipher algorithm?

问题描述

我发现很难理解在Hill Cipher算法中计算矩阵的逆的方式。我得到的想法，这一切都在模运算，但不知何故，事情不加起来。

考虑下面的Hill Cipher关键字矩阵：

 
 code> 5 8 
 17 3 
  

请使用上述矩阵进行说明。

解决方案

您必须学习 Linear congruence theorem and the extended GCD algorithm ，which belong到数字理论，以了解 modulo arithmetic 。

矩阵K的逆例如是（1 / det（K））* adjoint（K），其中det（K）≠0。 >

我假设您不了解如何计算

您的K已经在模数运算中用 1 / det（K） det（K）= - 121。假设模m是26.我们想要 x *（ - 121）= 1（mod 26）。
[a = b（mod m） * m]



我们可以很容易地发现，对于 x = 3 ，上述一致性是真的，因为26分（3 * 121）-1）。当然，正确的方法是使用GCD反向计算x，但我没有时间解释如何做。检查扩展的GCD算法:)

现在，inv（K）= 3 *（[3 -8]，[-17 5]） ）=（[9 -24]，[-51 15]）（mod 26）= （[9 2]，[115]）。

更新：，请查看计算数理论的基础，以了解如何使用扩展欧几里德算法计算模逆变。注意， -121 mod 26 = 9 ，因此 gcd（9,26）= 1 $ c>（ - 1，3）。

I am finding it very hard to understand the way the inverse of the matrix is calculated in the Hill Cipher algorithm. I get the idea of it all being done in modulo arithmetic, but somehow things are not adding up. I would really appreciate a simple explanation!

Consider the following Hill Cipher key matrix:

 5 8 
17 3

Please use the above matrix for illustration.

解决方案

You must study the Linear congruence theorem and the extended GCD algorithm, which belong to Number Theory, in order to understand the maths behind modulo arithmetic.

The inverse of matrix K for example is (1/det(K)) * adjoint(K), where det(K) <> 0.

I assume that you don't understand how to calculate the 1/det(K) in modulo arithmetic and here is where linear congruences and GCD come to play.

Your K has det(K) = -121. Lets say that the modulo m is 26. We want x*(-121) = 1 (mod 26).
[ a = b (mod m) means that a-b = N*m]

We can easily find that for x=3 the above congruence is true because 26 divides (3*(-121) -1) exactly. Of course, the correct way is to use GCD in reverse to calculate the x, but I don't have time for explaining how do it. Check the extented GCD algorithm :)

Now, inv(K) = 3*([3 -8], [-17 5]) (mod 26) = ([9 -24], [-51 15]) (mod 26) = ([9 2], [1 15]).

Update: check out Basics of Computational Number Theory to see how to calculate modular inverses with the Extended Euclidean algorithm. Note that -121 mod 26 = 9, so for gcd(9, 26) = 1 we get (-1, 3).

这篇关于如何计算Hill密码算法中的逆键矩阵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！