Aritmética modular
Con las congruencias podemos establecer un conjunto de operaciones aritméticas, como:
Siendo a, b, c, d ∈ Z y m ∈ N, tales que a ≡ b (mod (m)) y c ≡ d (mod (m)). Entonces,
a + c ≡ b + d (mod (m))
a · c ≡ b · c (mod (m))
(Recordemos que el signo ≡ significa “congruente con” y no es lo mismo que el signo = que significa “igual a”)
A partir de esto, podemos definir las propiedades aritméticas para las sumas de congruencias:
- Propiedad asociativa: a + (b + c) (mod (m)) = (a + b) + c (mod (m))
- Elemento neutro: Existe un elemento 0 ∈ Zm, tal que a + 0 (mod (m)) = a (mod (m))
- Elemento opuesto: Existe un elemento b ∈ Zm, tal que a + b = 0 (recordemos que 0 es el elemento neutro de la suma)
- Propiedad conmutativa: a + b (mod (m)) = b + a (mod (m))
También podemos definir las propiedades aritméticas para el producto de congruencias:
- Propiedad cancelativa: a · c ≡ b · c (mod (m)) y MCD (m, c) = 1, entonces a ≡ b (mod (m))
- Propiedad asociativa: a · (b · c) (mod (m)) = (a · b) · c (mod (m))
- Elemento neutro: Existe un elemento 1 ∈ Zm, tal que a · 1 (mod (m)) = a (mod (m))
- Elemento inverso: Existe un elemento a-1 ∈ Zm para todo a ∈ Zm con MCD (a, m) = 1, tal que a · a-1 = 1 (recordemos que 1 es el elemento neutro del producto)
Además de todas estas propiedades también se cumple la propiedad distributiva: a · (b + c) (mod (m)) = (a · b) + (a · c) (mod (m))
(Más información en la Wikipedia)
Para acabar, os voy a dar unos ejemplos de usos de las congruencias:
- En el DNI: La letra de tu NIF se realiza del siguiente modo: Número DNI (mod 23) y el resultado se pasa a una tabla que relaciona números con letras.
- En la generación de números seudoaleatorios: Los números aleatorios que genera cualquier ordenador se calculan usando una sucesión basada en congruencias: Xn+1 = (a · Xn + c) (mod (m))
- En criptografía: De este tema os hablaré dentro de poco, por ahora saber que las congruencias son la base de toda la criptografía moderna: RSA, El Gamal, …
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Bueno, no hizo falta, me puso un 9
PD: ¡Sabéis en lo que soy bueno! ¡En meter numeritos en cajitas!
Hola ! Soy maestra y justamente estoy buscando material de criptografia asociado a aritmética modular. Me podrías ayudar con alguna bibliografía?
Gracias!
cumic gracias por la corrección.
Respecto a los colores, me da que pronto cambiaremos el theme por uno de fondo blanco y fuente negra, además estamos buscando algo para tener las ecuaciones y fórmulas en imagenes.
Sobre criptografía, haber avisado de cuando te presentabas y me habría puesto las pilas.
Un par de cosillas:
– a · a-1 = 1 (mod m)
– Tenéis que retocar el css, el color gris de los blockquotes es muuuuuy parecido al negro, y contrasta muy poco.
Y una cosa más…
¡¡Bien, criptografía!! Auqnue eso lo podríais haber hecho antes de que me presentara ¬¬
bueno gracias por la explicación estuvo muy bien yo apenas estoy descubriendo que existe este tipo de matemática aunque tengo mucha curiosidad por el conocimiento matemático no conozco a nadie con quién discutir sobre estos temas mi poco aprendizaje algunos dirían que es vulgar pero bueno esto es algo que me gusta y me entretiene mucho espero un día ordenar mi conocimiento matemático Para estar ex muchas cosas. que me recomiendan Para tener mis ideas en orden y tener un orden en mi aprendizaje
hola buenos días soy necesito un concejo. como puede ser la forma mas rápida Para dominar las demostraciones en matemática recientemente me he interesado por esto , cualquier recomendación ayudaría mucho gracias
Buenas tardes amigos, investigando un tema, me he visto en la necesidad de calcular el módulo de una fracción , x=(a/b) mod c, donde a es un numero muuuuyyyyy grande.
se me olvidaba… ¡¡¡y lo he resuelto¡¡¡¡.