如何计算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*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).