Aritmética modular

La aritmética modular, también conocida como “aritmética del reloj”, debe su denominación a
que volvemos a contar desde el principio cuando alcanzamos un cierto valor, al que se llama
módulo.

Por ejemplo, cuando lo que contamos son horas, al llegar a 12, volvemos a empezar a contar
desde 1. Sin embargo, dado que un día tiene 24 horas, utilizamos dos sistemas diferentes: contar
de 24 en 24 o utilizar las iniciales a.m. (ante merídiem) para indicar las horas antes del mediodía
y p.m. (post merídiem) para indicar las horas después del mediodía.

Vamos a verlo con un ejemplo: las 17 horas es lo mismo que las 5 p.m., ya que 17 -5=12 (el
módulo).

Entonces podemos decir que 13=1, 14=2 y 24=12? Si, pero esto es sólo cierto cuando hablamos de
aritmética modular, por lo que lo correcto sería escribir.

Por ejemplo 13 ≡ 1 (mod 12) , que se lee “13 es congruente con 1 en módulo 12”, el valor 13 en este
caso, indica que da una vuelta completa de 12 hs y luego se posiciona en la hora 1.

El mismo ejemplo, pero si en lugar del módulo 12, usáramos módulo 7, el resultado es:
13 ≡ 6 (mod 7)

¿Y cómo se calcula?

Veamos algunas relaciones: en aritmética modular estamos interesados en conocer, de forma general,
expresiones del tipo: a ≡ b (mod. n) es decir, dado un valor ‘a’ queremos saber cuánto vale ‘b’ en
módulo ‘n’

Volviendo al ejemplo del reloj, que tiene tantas horas como lo indica la expresión ‘n’, y empezando a
mover la aguja (en sentido horario) hasta dar una vuelta completa (o las que hagan falta) y una vez
terminadas las vueltas completas, contar cuantas “horas” nos quedan hasta contar a horas. En el caso del
reloj de 12 horas (módulo 12) si nos dicen que calculemos el valor de 16 en módulo 12, daremos una
vuelta completa al reloj y luego contaremos 4 horas más, ya que 12 (1 vuelta completa) + 4 (horas que
faltan hasta llegar a 16) =16.

Podemos afirmar que si dividimos el valor de ‘a’ entre el valor de ‘n’ entonces el resto de la división es el
valor ‘b’. En el ejemplo anterior 16 (dividendo) = 12 (divisor) x 1 (cociente) + 4 (resto).
Algoritmo: Para calcular 16 mod 12 hacer lo siguiente:

1) Calcular 16 divido 12, entonces 16/12 = 1

2) Determinar el resto de la división entera, el resto es 4
3) Entonces podemos afirmar que : 16 mod 12 = 4

Congruencia

Queremos obtener un conjunto de números que módulo 12 tenga resto 4. La siguiente expresión nos
permitirá generar números que cumplen una determinada condición: x = a . 12 + r
x: número que se obtiene
a: equivale a la cantidad de vueltas, es un valor entero
r: es el resto, que siempre es un valor positivo

Entonces, luego de aplicar la formula anterior, obtenemos los siguientes números:

16 = 1 x 12 + 4
28 = 2 x 12 + 4
40 = 3 x 12 + 4

Los números 16 ,28 y 40 son congruentes porque respecto de módulo 12, su resto es 4.
La notación es: 40 ≡ 28 ≡ 16 ≡ 4 (mod 12)

De aquí se desprende que los restos posibles para un modulo 12, pueden ser: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10 y 11. Generalizando entonces 0 <= r <= n-1 (los valores de ‘r’, es un conjunto de números enteros
mayores o iguales a 0 y menor que ‘n’) Los restos en este caso son siempre positivos.

Como resolvemos la siguiente expresión?

Caso 1 : 1 mod 12

Se da el caso que 1 es menor que 12, cuál es el resultado de la operación? El resultado es 1. Todo valor
que sea menor que el modular da el mismo número porque está comprendido dentro del modulo. A
continuación explicamos el cálculo matemático que asegura esta afirmación.

1) Calcular 1 divido 12, entonces 1/12 = 0,083 periódico, redondeamos a 0,084

2) Determinar solo el valor decimal del cociente, en este caso 0,084
3) Multiplicamos 0,084 x n, que en este caso n=12, o sea 0,084 x 12 = 1,008
4) Tomamos como resultado 1, por lo tanto afirmamos que 1 mod 12 = 1

Este algoritmo se puede aplicar para cualquier valor modulo ‘n’

Caso 2 : -23 mod 5

Se da el caso que -23 es un número negativo, sabemos que los restos son positivos

1) Buscar un número menor más próximo a -23, y que sea múltiplo de 5

2) Para el caso es -25 , se obtiene de multiplicar ‘n’ por (-5), o sea 5 x (-5)
3) Calcular la diferencia entre |-25| y -23, nos da como resultado 2
4) -23 mod 5 = 2

Otro ejemplo: -81 mod 12,

Obtenemos que -7 x 12 = -84, entonces -84 < -81, es el numero buscado
|-84| es 84, entonces calculamos: 84 – 81 = 3, podemos afirmar que -81 mod 12 = 3
Ejercicios: verificar las siguientes congruencias, sin usar la función ‘mod’ de la calculadora:

1) 23595 mod 2007 = 1518

2) 1143962 mod 65537 = 29833

Ejercicios: Se muestran un reloj de 7 horas (modular 7) y otro de 12 horas ( modular 12)

1- Si el reloj marca la hora 2, se pide calcular para cada uno de los casos indicados, cuál es la hora
que marcará el reloj, al agregar la cantidad de horas indicada en la grilla?

Ejemplo: si inicialmente el reloj marca la hora 2, y transcurren 3 horas, procedemos a sumar el

numero 2 y el 3 , cuyo resultado es 5, entonces podemos afirmar que: 2 + 3 ≡ 5 (mod 7), el
resultado es 5

2- Cuál será el resultado si la aguja marca inicialmente el numero 5?

3- Obtener la hora que marcará el reloj, si inicialmente está en la hora 6, en un reloj modular 12,
si le sumamos las horas indicadas para los siguientes casos.

4- Combinando operaciones de suma y producto en aritmética modular, presentamos algunos

casos de cómo evaluar las expresiones. Se respetan el orden de resolución teniendo en cuenta
los términos que se generan ( operación + y - )

a) la expresión 2 x 4 ≡ 1 (mod 7), es correcto porque 2 x 4 = 8 y 8 mod 7 es 1

 b) 50 + 8*12 mod 27 es lo mismo que (50 mod 27 + 8*12 mod 27) mod 27.
En la primera expresión no hace falta poner paréntesis, realizamos toda la operación y al
final reducimos el resultado al módulo correspondiente. Es decir:
50 + 8*12 mod 27 = 146 mod 27 = 11
(50 mod 27 + 8*12 mod 27) mod 27 = (23 + 15) mod 27 = 38 mod 27 = 11

c) Verificar las siguientes igualdades:

1) 15*7-21 mod 27 = 3
2) 10-18*9 mod 26 = 4
3) 40*12 mod 60 = 0

d) Completar la grilla con los resultados correctos, aplicando suma y producto

Concepto de inverso aditivo

¿Qué son los inversos en un cuerpo? Como en la cifra realizaremos en emisión operaciones de suma y
multiplicación módulo n de los elementos del texto en claro con números o alguna clave, o
también suma or exclusivo módulo 2 en el caso de la cifra moderna, debemos asegurarnos de que
en el extremo receptor se pueda deshacer dicha operación y recuperar así el texto en claro. Para ello
usaremos los inversos, de manera que en el extremo receptor el destinatario de la cifra, conociendo
generalmente una clave, realizará la misma operación que en el extremo emisor, pero aplicando estos
valores inversos a los usados en emisión.

El inverso aditivo de un número en una operación suma dentro de un cuerpo n será el complemento de
ese número dentro del cuerpo.

Por ejemplo, en el cuerpo 27 el inverso aditivo de 12 será 15, puesto que 15+12 mod 27 = 0, que es la
identidad de la suma. Esto significa que si para cifrar se aplica en emisión un desplazamiento de 12
espacios a la derecha (sumar) en el alfabeto, es decir la letra F=5 se convierte en la letra Q=17, para
descifrar se puede desplazar el criptograma 12 espacios a la izquierda (restar), obteniendo
lógicamente la letra F inicial, o bien usar este inverso y sumar (no restar) 15 al criptograma, de forma
que Q + 15 = 17 + 15 = 32 mod 27 = 5 que es la letra F.

Como se puede observar, el inverso aditivo siempre existirá pues es simplemente el complemento de
cuerpo.

Ejercicio: Si la expresión inv+ (a, n) denota inverso aditivo del número a en el cuerpo n, encuentra los
siguientes inversos aditivos: inv+ (9, 27), inv+ (37, 64) , inv+ (-5, 31).

Solución: Los dos primero debes resolverlos tú mismo pues son muy sencillos. En el tercero, lo primero
que debes hacer es poner el número -5 en su forma canónica dentro del cuerpo 31, es decir su
equivalencia entre 0 y 30, simplemente sumando -5 + 31 mod 31 = 26 y resolver ahora inv+ (26, 31) = 5.
Observa que en este caso al ser el número a negativo, obviamente el inverso será siempre el mismo
número pero positivo; es decir inv+ (-18, 121) = 18, etc.

XOR o suma módulo 2

Un caso especial de inversos aditivos lo tenemos en la operación XOR y que se usará solamente en la
cifra moderna. La operación XOR equivale a una suma módulo 2, es decir usando como restos el
0 y el 1, por lo tanto aplicable al entorno de operaciones digitales.

Ejercicio: Resuelve las operaciones modulares que se indican: 7 mod 2; 4 mod 2, -3 mod 2, 3*9 mod 2.

Solución: En módulo 2 las operaciones son muy simples: números impares dan como resultado un 1 y
números pares dan como resultado un 0. Esto es lo mismo que aplicar la tabla de verdad de esta
operación, que indica que el XOR entre bits de igual valor entrega un 0 y el XOR entre bits de valores
distintos entrega un 1. Así, 1 XOR 1 XOR 1 = 1, porque 1 XOR 1 = 0 y 0 XOR 1 = 1.

Observa que dado que los restos del módulo 2 son el 0 y el 1, este número no tiene inversos en el
sentido que lo tienen los demás números. El inverso del or exclusivo es o XOR el mismo valor, dado que
la operación XOR es involutiva, es decir aplicado dos veces se obtiene la identidad.

Recuerda que la operación se hace bit a bit y los números no tienen por qué ser el 0 y el 1; de hecho, por
lo general serán números mucho mayores. Por ejemplo si hacemos un XOR entre los números decimales
19 y 30 tendremos: 19 XOR 30 = 13. ¿Por qué? Ahora lo veremos. El número 19 en binario es 10011 y 30
en binario es 11110; si realizamos la suma XOR bit a bit, se obtiene: 01101 que es igual a 13. Otro
ejemplo con tamaños distintos de bits: 27 XOR 50 = 41, porque 27 = 11011 (de cinco bits) y 50 = 110010
(de seis bits) y 011011 XOR 110010 = 101001 = 41.

¿Y cuáles son los inversos? Si 27 XOR 50 = 41, entonces el inverso de 27 es 50 y el inverso de 50 es

21. Vamos a comprobarlo, suponiendo que el mensaje es 27 y la clave 50. Si realizamos la cifra,
27 XOR 50 = 41 como ya hemos visto. Para descifrar este criptograma numérico 41 y recuperar el
secreto, haremos 41 XOR 50 = 101001 XOR 110010 = 011011 = 27, y hemos recuperado el secreto.

Ejercicio: cifrar el mensaje LUZ con la clave abc

Solución: primero obtener los valores decimales ASCII y después bit a bit. O sea convertir este valor
decimal a binario. Ayuda. ASCII decimal: L = 76, U = 85, Z = 90, a = 97, b = 98, c = 99.

L XOR a = 76 XOR 97 = 45 = - (carácter ASCII)

U XOR b = 85 XOR 98 = 55 = 7 (carácter ASCII)

Z XOR c = 90 XOR 99 = 57 = 9 (carácter ASCII)

Para descifrar el criptograma en ASCII -79 aplicamos la clave abc y obtenemos el texto en claro LUZ.

Concepto de inverso multiplicativo

Se dice que un número a, elemento o resto del cuerpo n, tiene inverso multiplicativo en dicho cuerpo, o
simplemente inverso, si existe otro número x que haga cumplir la condición de que: a * x mod n = 1
Es decir, que al multiplicar el valor de a por el valor de x y reducirlo módulo n, se obtenga como
resultado el valor 1, que es la identidad de la multiplicación.

Viendo la ecuación anterior y aunque matemáticamente no sea correcto decirlo, por simplicidad y para
que podamos recordarlo, podríamos asociar el concepto del inverso a que a = 1/x o bien que x = 1/a en
ese cuerpo n. Observa que en aritmética modular no es lo mismo decir que x = 1/a mod n (lo cual no
está permitido) a que x = a-1 mod n o bien que x = inv (a, n), que sí son expresiones correctas.

Visualización de inversos

Sea el cuerpo n = 10 con elementos o restos {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. A excepción del 0 y del 1 donde
no tiene sentido hablar de estos inversos porque nunca multiplicaremos por 0 ni por 1 en una cifra, los
únicos elementos en 10 que tendrán inversos son el 3, el 7 y el 9, pues el máximo común divisor de
estos números y el módulo 10 es igual a 1.

Para comprobar que el número 3 tiene inverso en 10, podríamos multiplicar todos los elementos
de n por 3 y reducir el resultado módulo 10. Veamos qué sucede.

Realizando esta operación con los 10 elementos del cuerpo, observamos que se obtienen todos los
restos del número 10, del 0 al 9, y que solamente en el caso de x = 7 obtenemos el resultado 1 que
estábamos esperando.

Por lo tanto, el inverso de 3 en el cuerpo 10 es 7, de la misma manera que el inverso de 7 en el cuerpo

10 es 3. Además, y esto será muy importante en criptografía, ese valor será único.

Ejercicio: Realiza la misma operación para encontrar el inverso de 4 en módulo 10, esto es multiplicando
4 por todos los restos de 10 y reduciendo el resultado módulo 10, para comprobar que no existe el
inverso del 4 en módulo 10.

Ejercicio: Ahora ciframos el mensaje IMPOSIBLE en módulo 27 multiplicando cada letra por 3.
Hecho esto intenta descifrar multiplicando el resultado por cualquier número dentro del cuerpo 27 y
verás que es imposible recuperar el texto en claro. Nota: no hace falta que lo hagas con todo el
mensaje; puedes comprobarlo sólo con el primer carácter I = 8 que al multiplicarlo por 3 se
obtiene 24 = X. Multiplica ese valor 24 (la X) por todos los restos en mod 27 a ver si obtiene el 8 de la
letra I.

Solución: 24*2 mod 27 = 21, 24*3 mod 27 = 18, 24*4 mod 27 = 15, 24*5 mod 27 = 12, 24*6 mod 27 = 9,
24*7 mod 27 = 6, 24*8 mod 27= 3, 24*9 mod 27 = 0, 24*10 mod 27 = 24, 24*11 mod 27 = 21… y la
cadena 21, 18, 15, 12, 9, 6, 3, 0 se repite, sin aparecer nunca el 8 que estamos buscando. No se ha
calculado la operación con el resto 1 porque este valor nunca se usa para multiplicar el texto en la cifra
clásica.
Algoritmo Extendido de Euclides AEE.

El cálculo de inversos, en este caso multiplicativos, es una derivación del famoso teorema de Euclides
con el que éramos capaces de encontrar el máximo común divisor entre dos números. La idea básica es
que si entre dos números a y n no existen factores en común, entonces el máximo común divisor entre
ellos será igual a 1. Y precisamente desde ese valor de la unidad podremos realizar un camino en sentido
contrario en el algoritmo de Euclides, para llegar a ese inverso buscado que nos dice que si mcd (a, n) =
1 entonces existe el inverso de a en el cuerpo n, es decir inv (a, n). Este procedimiento se conoce como
Algoritmo Extendido de Euclides AEE.

Existen diversas formas de encontrar el inverso multiplicativo del número a en módulo n mediante este
algoritmo. A continuación se describe una de ellas. Las ecuaciones que regirán para calcular x = inv (a, n)
son las siguientes:
Vamos a encontrar el inverso de 9 en el cuerpo 275, esto es inv (9, 275). Sabemos que el inverso existe
pues mcd (9, 275) = 1, dado que 9 = 32 y 275 = 52x11. En la figura 2.5 se recogen los pasos del algoritmo.

Como vi-1 = -61, es decir ha salido un valor negativo, entonces X = - 61 + 275 = 214
Efectivamente, inv (9, 275) = 214 pues 214 x 9 = 1.926 mod 275 = 1, ya que 1.926 = 7 x 275 + 1

Ejercicio: usar el Algoritmo Extendido de Euclides haciendo una tabla similar y encuentra el inverso de
17 en módulo 315 es decir inv (17, 315) y el inverso de 123 en el cuerpo 1.000 es decir inv (123, 1.000).
Verifica que los valores encontrados de los inversos son los correctos.

La exponenciación en aritmética modular

En aritmética módulo n la exponenciación modular es menos costosa de realizar que en la aritmética
entera. Nótese que a.b mod n = [(a mod n) (b mod n)] mod n, y que por grande que sea el exponente,
nunca es necesario multiplicar por enteros mayores que n.

Además hay un método que nos permite ahorrar pasos de cálculo. La forma más obvia para calcular por
26
ejemplo, 12 (mod 23) es multiplicar por 12 un total de 25 veces, reduciendo módulo 23 tras cada
multiplicación. Pero un método más eficiente que solo necesita seis multiplicaciones está a nuestra
mano si nos damos cuenta de lo siguiente:

Nuestro algoritmo consiste pues en descomponer el exponente como potencias de 2, es decir, escribirlo
en base 2 y multiplicar sucesivos cuadrados del entero base de la exponenciación por cada dígito binario
del exponente que sea un "1". En el ejemplo anterior, el exponente es 26(10)= 11010(2)

Con esto hemos hecho cuatro cuadrados, y como podemos descomponer el exponente en potencias
de 2, así 26=16+8+2, y podemos reescribir el cálculo anterior como:

26 (16+8+2) 16 8 2
12 =12 =12 *12 *12 =18*8*6=864≡ 13 (mod 23)

2 8 16
12 =144=6 (mod 23) 12 =132=169=8 (mod 23) 12 =82=64=18 (mod 23)

Nota: para pasar de un numero binario a decimal, usando el ejemplo anterior, aplicamos el método
4 3 2 1 0
26 = 1x2 + 1x2 + 0x2 + 1x2 + 0x2 = 16 + 8 + 0 + 2 + 0 = 16 + 8 + 2
Pequeño Teorema de Fermat

Dos números enteros son coprimos o primos entre sí si su máximo común divisor (mcd) es 1
p-1
También se puede decir de otra forma, si p es primo y p no divide a a entonces: a ≡ 1 (mod p)

38
Verificamos si 5 es 4 modulo 11, aplicando el pequeño teorema de Fermat
 44
Calcular 7 modulo 13:

Fuente: https://youtu.be/aj2lq71FPtQ
Protocolos basados en aritmética modular: Diffie-Hellman

Recordemos que el protocolo Diffie-Hellman, mediante el uso de claves públicas, permite establecer
una clave simétrica de sesión, la cual es generada o negociada entre los dos equipos en el momento que
se conectan entre si.
Presentamos en caso que B quiere comunicarse con A, para lo cual le solicita sus claves públicas. A envía
x
los valores ( g,n, g mod n), sean g= 5, n=23 como claves publicas y x=6 la clave privada de A, e Y=15 la
clave privada de B.
Recordar que las claves privadas son secretas y ningún equipo las divulga. Para el ejercicio se muestran
los valores para comprobar el funcionamiento del algoritmo.
6
A: calcula 5 mod 23 que es igual a 8
Envía los valores 5, 23, 8
y 15
B: recibe 5, 23, 8 y procede a calcular g mod n, o sea 5 mod 23, que es igual a 19
Ese valor, el 19, es el que le envía a A
15
Ademas calcula 8 mod 23 y obtiene el valor 2, que es la clave simétrica de sesión
6
A: recibe el valor 19, al cual le aplica su clave privada, entonces 19 mod 23 = 2

Como se puede observar, tanto A como B, al final del intercambio de claves, obtienen el valor de clave
simétrica de sesión, que es igual a 2
Con esa clave = 2, comenzarán a cifrar los mensajes de acuerdo a un protocolo previamente acordado,
como por ejemplo el DES, o también puede ser el AES