How to calculate the inverse key matrix in Hill Cipher algorithm?
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.
Answer
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.
The inverse of matrix K for example is (1/det(K)) * adjoint(K), where det(K) <> 0.
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.
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 :)
Now, inv(K) = 3*([3 -8], [-17 5]) (mod 26) = ([9 -24], [-51 15]) (mod 26) = ([9 2], [1 15]).
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).