views:

2431

answers:

5

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.

+3  A: 

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

Nick D
Thank You tydok!
Amit
Cheers! :) -
Nick D
A: 

according to def if k^-1 is said to be inverse of k then k*k^-1 = I.

I means identity matrix having diagonal elements having '1' and rest all having '0'

please verify the answer

It's modulo arithmetic, where m=26. K*inv(K)= ([53 130], [156 79])(mod 26) = ([1 0], [0, 1]) (mod 26).
Nick D
A: 

nice truncatd soln man ...thnx!!

A: 

really its is a very good description about the algorithm

Hardik
A: 

how to find the value of x in inverse calcuation

ravi magardey