Cómo calcular la matriz inversa clave de cifrado en la colina algoritmo?

Question

Me resulta muy difícil de entender cómo es el inverso de la matriz se calcula en el algoritmo de cifrado de Hill. Me da la idea de que todo se hace en la aritmética de módulo, pero de alguna manera las cosas no están sumando. Realmente agradecería una explicación simple!

Considere la siguiente matriz de teclas Colina Cipher:

 5 8 
17 3

Utilice la matriz anterior para la ilustración.

Answer 1

Debe estudiar el lineal teorema de congruencia y la extendido algoritmo GCD, que pertenecen a Teoría de números , con el fin de entender las matemáticas detrás módulo aritmético .

La inversa de la matriz K por ejemplo, es (1 / det (K)) * adjunto (K), donde det (K) <> 0.

Asumo que usted no entiende cómo calcular el 1 / det (K) en la aritmética de módulo y aquí es donde congruencias lineales y GCD vienen a jugar.

Su K tiene det (K) = -121. Digamos que el módulo m es 26. Queremos x *. (- 121) = 1 (mod 26)
[a = b (mod m) significa que ab = N * m]
Podemos encontrar fácilmente que para x = 3 la congruencia anterior es cierto, porque las divisiones 26 (3 * (- 121) -1) exactamente. Por supuesto, la forma correcta es utilizar GCD a la inversa para calcular la x, pero no tiene tiempo para explicar cómo hacerlo. Compruebe el algoritmo GCD extented :)

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

Actualización: Fundamentos de Número Computacional teoría para ver cómo calcular inversos modulares con el algoritmo de Euclides extendido. Tenga en cuenta que -121 mod 26 = 9, por lo que para gcd(9, 26) = 1 obtenemos (-1, 3).

Answer 2

En mi muy humilde opinión es mucho más fácil para el cálculo de la matriz inversa (modular o no) mediante el método de Gauss-Jordan. De esa manera usted no tiene que calcular el determinante, y el método de las escalas de forma muy sencilla a los sistemas arbitrariamente grandes.

Sólo busca 'Gauss Jordan matriz inversa' - pero para resumir, sólo tiene que colindan con una copia de la matriz de identidad a la derecha de la matriz para ser invertida, a continuación, utilizar operaciones de fila para reducir su matriz para ser resuelto hasta que en sí es una matriz de identidad. En este punto, la matriz de identidad contiguo se ha convertido en la inversa de la matriz original. Voila!