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

问题描述

我发现它很难理解矩阵的逆计算在希尔加密算法的方式。我得到这一切的想法是在模运算完成的，但不知何故，事情并没有加起来。我真的AP preciate一个简单的解释！

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.

推荐答案

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

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.

的矩阵K例如的倒数（1 / DET（K））*伴随（K），其中，DET（K）＆所述;> 0

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

我以为你不知道如何计算 1 / DET（K） 在模运算和这里是线性同余和GCD来打。

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.

您K有DET（K）= -121。让我们说，模M是26，我们希望的 X 。*（ - 121）= 1（模26）
[A = B（模m）是指AB = N * M]

我们不难发现，对于 X = 3 上面的一致性是真实的，因为26除以（3 *（ - 121）-1）完全吻合。当然，正确的方法是使用GCD在反向计算X，但我没时间解释如何做到这一点。检查推广的GCD算法:)

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 :)

现在，INV（K）= 3 *（[3-8]，[-17 5]）（MOD 26）=（[9 -24]，[-51 15]）（MOD 26）= <强>（[9 2]，[1 15]）

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

更新：看看基础计算的数论怎么看计算模块化逆与扩展欧几里德算法。需要注意的是 -121mod26 = 9 ，所以 GCD（9，26）= 1 我们得到。（ - 1,3）

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).

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