Aritmética modular

En este post, daremos unas pinceladas de un tema extremadamente importante en Criptografía (y en muchas otras áreas de las Matemáticas): la aritmética modular.

Antes de empezar, tengo una pregunta muy sencilla que seguro que sabes contestar. Si ahora son las 11 según nuestro reloj de pared, ¿qué hora marcará dentro de 2 horas? Exacto, la 1. ¿No te parece un poco raro? Si sumamos 2 a 11, el resultado es 13, no 1. ¿Por qué decimos que las 13 horas es lo mismo que la 1? Porque, en el reloj, al dar una vuelta y llegar a las 12, volvemos a empezar la circunferencia desde el principio.

Algo muy similar ocurría, por ejemplo, con el cifrado César, en el que desplazábamos un número fijo cada letra hacia adelante en el alfabeto. Si ese número era 3, por ejemplo, y la letra que queríamos cifrar era la X, lo que hacíamos era volver a empezar desde el principio del alfabeto, ya que no hay ninguna letra 3 posiciones después de la X, y llegábamos a la A.

Como vemos, existen muchos ejemplos de este comportamiento tanto en la vida cotidiana como en el ámbito matemático.

Consideremos el conjunto de todos los números naturales menores que 12: S={0,1,2,3,4,5,6,7,8,9,10,11}, que se corresponde con las 12 horas del reloj. Obviamente, 15 no pertenece a este conjunto, ni tampoco 27. Pero queremos que "en esencia", 15 y 27 sean lo mismo que 3. Esto motiva la siguiente definición:

Definición: sean a y r números enteros. Decimos que a y r son "congruentes en S", y lo denotamos "a ≡_S r", si 12 divide a a-r. Llamamos a r el "resto".

Ahora sí que podemos decir que 3 ≡_S 15 ≡_S 27. ¿Con cuál de los elementos de S sería congruente 58? Lo único que tenemos que hacer es calcular el resto de la división 58/12, que es 4. Así, 58 ≡_S 4.

Podríamos definir una suma en S de forma que el resultado siempre vuelva a caer en el conjunto:

Definición: sean a,b ∈ S. La suma de a y b cumple a+b ≡_S c, con c ∈ S.

Por ejemplo, 2+3 ≡_S 5, 7+6 ≡_S 1, 1+11 ≡_S 0 y 10+10 ≡_S 8.

De forma análoga, definiríamos el producto:

Definición: sean a,b ∈ S. El producto de a y b cumple a*b ≡_S c, con c ∈ S.

Por ejemplo, 2*3 ≡_S 6, 7*6 ≡_S 6, 1*11 ≡_S 11 y 10*10 ≡_S 4.

Estas dos operaciones, cumplen varias propiedades. Por ejemplo, existe un neutro para la suma, que es el 0 (0+a ≡_S a, para cualquier a ∈ S); existe un neutro para el producto, que es el 1 (1*a ≡_S a, para cualquier a ∈ S); existe inverso aditivo (para todo a ∈ S, existe un número (-a) ∈ S tal que a+(-a) ≡_S 0).

Por ejemplo, 7 es el inverso aditivo de 5 porque 7+5 ≡_S 0.

En cuanto al inverso multiplicativo (que normalmente llamamos sólo "inverso"), sólo existe para algunos números. Por ejemplo, 5 es su propio inverso, ya que 5*5 ≡_S 1. Los únicos elementos de S para los que existe inverso multiplicativo son 1, 5, 7 y 11. Curiosamente, cada uno de estos cuatro números es su propio inverso.

Hemos estado trabajando con S={0,1,2,3,4,5,6,7,8,9,10,11}. Pero podríamos utilizar cualquier conjunto de la forma {0,1,...,m-1}, con m un número natural. Llamaremos a este conjunto ℤ_m. En particular, nuestro S es igual a ℤ₁₂. Y, de manera análoga, podríamos definir las congruencias módulo m:

Definición: sean a, r, m números enteros, con m>0. Decimos que a y r son "congruentes módulo m", y lo denotamos "a ≡ r (mod m)", si m divide a a-r. Llamamos a r el "resto" y a m, el "módulo".

Así, 33 ≡ 3 (mod 15), 9 ≡ 0 (mod 3) y 82 ≡ 5 (mod 7).

Es fácil ver cómo se generalizan nuestras dos operaciones de antes:

Definición: sean a,b ∈ ℤ_m. La suma de a y b cumple a+b ≡ c (mod m), con c ∈ ℤ_m. El producto de a y b cumple a*b ≡ d (mod m), con d ∈ ℤ_m.

¿Has oído hablar de los números binarios, que son la base de la informática? Pues no son otra cosa que ℤ₂={0,1}. De esta forma, 1+1≡0 (mod 2).

Para terminar, existe un resultado que dice que para un número a ∈ ℤ_m, existe un inverso multiplicativo si y sólo si mcd(a,m)=1 (el máximo común divisor de a y m). En ese caso, se dice que a y m son "primos relativos".

Por esa razón, teníamos tan pocos números con inversos en S, porque 12 tiene muchos divisores. Además, si m es un número primo, todos los números no nulos a ∈ ℤ_m tendrán inverso, porque mcd(a,m) será siempre 1. Por esto mismo, se suelen utilizar aritmética modular con primos, porque se comportan mejor que el resto de números.

Espero que te hayas hecho una idea general de cómo funciona la aritmética modular, pues la utilizaremos en nuestro siguiente cifrado, que es una generalización del César.