Parte 1: Aritmética Modular

La premisa del algoritmo de cifrado de Hill es convertir letras de texto llano en letras de texto críptico mediante sistemas de ecuaciones lineales y sus formas matriciales. El descifrado solo necesita hacer una transformación inversa, la clave es la propia matriz de transformación. A continuación se definen los conceptos matemáticos a usarse para el encriptado de Hill-II.

Modulos:

Dados dos números enteros, a (el dividendo) y n positivo (el divisor), a módulo n (abreviado como a mod n) es el resto de la división euclídea de a por n. Esto es a mod n = r donde r está definido de la siguiente manera:

Con R definido de la forma: R = resto de |a| dividido para m.

Por ejemplo, la expresión 10 mod 3 se evaluaría a 1 porque 10 dividido por 3 da un cociente de 2 y un resto de 1, mientras que 12 mod 3 se evaluaría a 0 porque la división de 12 entre 3 tiene un cociente de 4 y da un resto de 0. Es decir:

Inversos Modulares:

En aritmética modular, un número a tiene un inverso modular a elevado a la -1 Mod m si se verifica la siguiente propiedad:

Por ejemplo, el inverso modular de 9 para mod 26:

Esto quiere decir que 3 es inverso modular de 9 por mod 26.

Congruencia modular:

Se dice que dos enteros A y B comparten clase de congruencia Mod n si al dividirlos entre n arrojan el mismo resto, o de forma equivalente, si A − B es múltiplo de n. Esto es: A ≡ B (Mod C). Se lee A es congruente con B módulo C. Por ejemplo:

Por lo tanto, 31 y 16 están en la misma clase de equivalencia para 1.

Números coprimos:

Números coprimos (números primos entre sí o primos relativos) son dos números enteros a y b que no tienen ningún factor primo en común. Por ejemplo, 4 y 17 son primos entre sí, pero 4 y 6 no lo son porque ambos son divisibles por 2. El 1 es primo respecto de todos los enteros, mientras que 0 sólo lo es respecto de 1 y -1.