如何计算丘陵密码算法中的反键矩阵？

Question

我发现很难理解在山丘密码算法中计算矩阵的倒数的方式。我了解了这一切都在Modulo算术中完成的，但是某种程度上并没有加起来。我真的很感谢一个简单的解释！

考虑以下Hill Cipher键矩阵：

 5 8 
17 3

请使用上面的矩阵进行插图。

Answer 1

您必须研究 线性一致定理 和 扩展的GCD算法, ，属于 数字理论, ，为了理解背后的数学 模型算术.

例如，矩阵k的倒数为（1/det（k）） *伴随（k），其中det（k）<> 0。

我认为您不明白如何计算 1/det（k） 在Modulo算术中，这是线性一致性和GCD开始播放的地方。

您的k具有det（k）= -121。假设Modulo 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

以我的拙见，使用高斯 - 乔丹方法来计算逆矩阵（模块化或其他方式）要容易得多。这样，您就不必计算决定因素，而方法则非常简单地缩放到任意大型系统。

只需查找'高斯乔丹矩阵倒数' - 但总而言之，您只需在矩阵的右侧与身份矩阵的副本相结合，然后使用行操作来减少要求解的矩阵，直到其本身为身份是一个身份矩阵。此时，相邻的身份矩阵已成为原始矩阵的倒数。瞧！