How to calculate the inverse key matrix in the Hill Slate algorithm?

Question

It is very difficult for me to understand how the inverse matrix is ​​calculated in the Hill Cipher algorithm. I understand that all this is done modulo arithmetic, but for some reason things do not add up. I would really appreciate a simple explanation!

Consider the following Hill Cipher key matrix:

5 8 17 3 

Use the matrix above to illustrate.

Answer 1

You must study the Linear Congruence Theorem and the advanced GCD algorithm that relate to Number Theory in order to understand mathematics beyond modulo arithmetic .

The inverse matrix K, for example, is (1 / det (K)) * conjugate (K), where det (K) & lt> 0.

I assume that you do not understand how to calculate 1 / det (K) modulo, but here linear congruences and GCD appear.

Your K has det (K) = -121. Suppose that the module m is 26. We want x * (- 121) = 1 (mod 26).
[a = b (mod m) means that ab = N * m]

It is easy to find that for x = 3 the above congruence is true because 26 divides (3 * (- 121) -1) exactly. Of course, the right way is to use GCD in the reverse order to calculate x, but I don't have time to explain how to do this. Check out the advanced 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 Fundamentals of Computational Number Theory to learn how to calculate modular callbacks with an advanced Euclidean algorithm. Note that -121 mod 26 = 9 , so for gcd(9, 26) = 1 we get (-1, 3) .