algorithm - 如何计算希尔密码算法中的逆密钥矩阵？

Question

我发现很难理解在希尔密码算法中计算矩阵逆的方式。我知道这一切都是在模算术中完成的，但不知何故，事情并没有加起来。我真的很感激一个简单的解释！

考虑以下 Hill Cipher 密钥矩阵：

 5 8 
17 3

请使用上面的矩阵进行说明。

Answer 1

您必须学习线性同余定理和扩展 GCD 算法，它们属于数论，以了解模运算背后的数学。

例如矩阵 K 的逆矩阵是 (1/det(K)) * adjoint(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*m]

我们可以很容易地发现，对于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)。

Answer 2

在我非常拙见的意见中，使用 Gauss-Jordan 方法计算逆矩阵（模块化或其他）要容易得多。这样您就不必计算行列式，并且该方法可以非常简单地扩展到任意大型系统。

只需查找'Gauss Jordan Matrix Inverse' - 但总而言之，您只需将单位矩阵的副本连接到要反转的矩阵的右侧，然后使用行操作来减少要解决的矩阵，直到它本身是一个单位矩阵。此时，邻接的单位矩阵已经成为原矩阵的逆矩阵。瞧！