How do you find inverse of matrix in hill cipher technique? - Answers

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