Me resulta muy difícil comprender la forma en que se calcula el inverso de la matriz en el algoritmo de Hill Cipher. Me da la idea de que todo se hace en aritmética modular, pero de alguna manera las cosas no se suman. ¡Realmente apreciaría una explicación simple!¿Cómo se calcula la matriz de clave inversa en el algoritmo de Hill Cipher?
Considérese la siguiente colina Cipher matriz de teclas:
5 8
17 3
Utilice la matriz anterior para la ilustración.
Debe estudiar la Linear congruence theorem y la extended GCD algorithm, que pertenecen a Number Theory, con el fin de entender las matemáticas detrás de modulo arithmetic.
La inversa de la matriz K es, por ejemplo, (1/det (K)) * adjunto (K), donde det (K) <> 0.
Asumo que usted no entiende cómo calcular el 1/det(K) en aritmética de módulo y aquí es donde entran en juego las congruencias lineales y el GCD.
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 26 divisiones (3 * (- 121) - 1) exactamente Por supuesto, la forma correcta es usar GCD en reversa para calcular la x, pero no tengo tiempo para explicar cómo hacerlo. Verifique el algoritmo GCD extendido :)
Ahora, inv (K) = 3 * ([3 -8], [-17 5]) (mod 26) = ([9 -24], [-51 15 ]) (mod 26) = ([9 2], [1 15]).
Actualización: la salida Basics of Computational Number Theory 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).
¡Salud! :) - –