Comment calculer la matrice inverse clé Hill algorithme Cipher?

Question

Je trouve qu'il est très difficile de comprendre la façon dont l'inverse de la matrice est calculée dans la colline algorithme Cipher. Je reçois l'idée de tout cela se fait dans l'arithmétique modulo, mais en quelque sorte les choses ne sont pas additionner. J'apprécierais vraiment une explication simple!

Considérons la colline suivante Cipher matrice clé:

 5 8 
17 3

S'il vous plaît utiliser la matrice ci-dessus pour illustration.

Answer 1

Vous devez étudier la théorème de congruence linéaire et algorithme GCD étendu , qui appartiennent à Théorie des nombres , afin de comprendre les mathématiques derrière modulo arithmétique .

L'inverse de la matrice K est par exemple (1 / det (K)) * adjoint (K), où det (K) <> 0.

Je suppose que vous ne comprenez pas comment calculer le 1 / det (K) en arithmétique modulo et voici où congruences linéaires et GCD viennent jouer.

Votre K a det (K) = -121. Disons que le modulo m est 26. Nous voulons x *. (- 121) = 1 (mod 26)
[a = b (mod m) signifie que ab = N * m]
Nous pouvons facilement constater que pour x = 3 congruence ci-dessus est vrai parce que 26 divise (3 * (- 121) -1) exactement. Bien sûr, la bonne façon est d'utiliser GCD dans le sens inverse pour calculer les x, mais je n'ai pas le temps pour expliquer comment le faire. Vérifiez l'algorithme de GCD extented :)

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

Mise à jour: Bases de calcul Nombre théorie pour voir comment calculer modulaires avec l'inverses algorithme d'Euclide étendu. Notez que -121 mod 26 = 9, donc pour gcd(9, 26) = 1 nous obtenons (-1, 3).

Answer 2

Dans mon très humble avis, il est beaucoup plus facile de calculer la matrice inverse (modulaire ou autre) en utilisant la méthode Gauss-Jordan. De cette façon, vous n'avez pas de calculer le déterminant, et la méthode des échelles très simplement aux systèmes arbitrairement grands.

Il suffit de regarder Gauss Jordan matrice inverse »- mais pour résumer, vous Adjoignons simplement une copie de la matrice d'identité à droite de la matrice à inverser, puis utilisez les opérations de ligne pour réduire votre matrice à résoudre jusqu'à ce qu'il se est une matrice d'identité. A ce stade, la matrice identité accolée est devenue la inverse de la matrice d'origine. Le tour est joué!