Hill Cipher算法中如何计算逆密钥矩阵？
我发现很难理解希尔密码算法中矩阵逆的计算方式。 我知道这一切都是通过模算术完成的，但不知何故，事情并没有加起来。 我真的很感激一个简单的解释！
考虑以下希尔密码密钥矩阵：
5 8
17 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您必须研究线性同余定理和扩展 GCD 算法，属于 数论，为了理解模算术背后的数学原理。
矩阵K的逆例如是(1/det(K))*adjoint(K)，其中det(K)＜＞ 0.
我假设您不明白如何计算1/det(K)< /strong> 在模算术中，这就是线性同余和 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]) (mod 26) = ([9 -24], [-51 15]) (mod 26) = ([9 2], [1 15])。
更新：查看计算数基础知识理论了解如何使用扩展欧几里德算法计算模逆。 请注意，
-121 mod 26 = 9，因此对于gcd(9, 26) = 1，我们得到(-1, 3)。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 forgcd(9, 26) = 1we get(-1, 3).在我看来，使用 Gauss-Jordan 方法计算逆矩阵（模矩阵或其他矩阵）要容易得多。 这样您就不必计算行列式，并且该方法可以非常简单地扩展到任意大的系统。
只需查找“高斯乔丹矩阵逆” - 但总而言之，您只需将单位矩阵的副本连接到要求逆的矩阵的右侧，然后使用行运算来减少要求解的矩阵，直到它本身是一个单位矩阵。 此时，邻接的单位矩阵已成为原始矩阵的逆矩阵。 瞧！
In my very humble opinion it is much easier to calculate the inverse matrix (modular or otherwise) by using the Gauss-Jordan method. That way you don't have to calculate the determinant, and the method scales very simply to arbitrarily large systems.
Just look up 'Gauss Jordan Matrix Inverse' - but to summarise, you simply adjoin a copy of the identity matrix to the right of the matrix to be inverted, then use row operations to reduce your matrix to be solved until it itself is an identity matrix. At this point, the adjoined identity matrix has become the inverse of the original matrix. Voila!