Aritmética modular

Decir que un número a es congruente con b módulo m significa que a y b dejan el mismo resto al dividir entre m, o lo que es igual, que su diferencia es múltiplo de m. El módulo m fija cuántos restos hay: de cero a m menos uno.

El resto como operación

• El operador módulo devuelve el resto de dividir entre m.
• Todo número se reduce a uno de los m restos posibles.
• Es la función que convierte la recta entera en un círculo de m casillas.

Sumar y multiplicar en módulo

Se puede sumar o multiplicar y luego reducir al resto: dar el resto al final o en cada paso lleva al mismo resultado. Esta compatibilidad hace que la aritmética modular sea un sistema algebraico manipulable, no solo un truco.

Propiedades útiles

• El resto de una suma depende solo de los restos de los sumandos.
• Se puede reducir intermedio para no manejar números enormes.
• Las potencias se calculan por exponenciación modular sin desbordar.

Un ejemplo con el reloj

Si son las nueve y pasan cinco horas, son las dos, no las catorce: trabajamos módulo doce. La aritmética del reloj es exactamente aritmética modular, y ayuda a intuir por qué los resultados «dan la vuelta».

Inverso modular

• No toda división es posible: hace falta un inverso multiplicativo.
• Un número tiene inverso módulo m si es coprimo con m.
• Ese inverso es la pieza que habilita la resta y la división en módulo.

Números coprimos y mcd

Dos números son coprimos cuando su máximo común divisor vale uno. La existencia de inverso modular depende de esa coprimalidad, y el algoritmo de Euclides la comprueba y la construye.

Aplicación: hashing

• Un resumen de datos puede reducirse módulo una tabla para elegir posición.
• La dispersión de restos decide colisiones y rendimiento.
• Elegir un módulo primo suele mejorar la uniformidad.

Aplicación: checksums y códigos

El dígito de control de un documento o de una tarjeta se calcula con módulo. Detectar errores de transcripción es, en el fondo, comprobar una congruencia que debe cumplirse.

Aplicación: criptografía

• La seguridad RSA se apoya en aritmética modular con números enormes.
• Operaciones con primos grandes y sus restos forman trampas difíciles de invertir.
• Entender módulo es entender por qué el cifrado funciona.

Ciclos y periodicidad

Al avanzar de resto en resto, todo se repite con periodo m. Esa periodicidad modela agendas rotativas, ruedas de entidades y cualquier proceso que vuelve a su estado tras un número fijo de pasos.

Errores frecuentes

• Olvidar reducir y trabajar con números que desbordan.
• Confundir congruencia con igualdad: a es equivalente a b, no igual.
• Dividir sin comprobar que existe el inverso modular.

Ejemplo resuelto: dar la vuelta al reloj

Son las siete y quieres saber qué hora será dentro de cien horas. Reduce el problema módulo doce.

1. Suma las horas transcurridas: siete más cien dan ciento siete.
2. Divide ciento siete entre doce y quédate con el resto.
3. Doce por ocho es noventa y seis, así que el resto es once.
4. Por tanto, dentro de cien horas serán las once.
5. Comprueba que restar vueltas completas de doce no cambia la hora.

¿Para qué sirve en la realidad?

La aritmética modular está en el dígito de control de tarjetas y documentos, en el reparto de datos entre servidores mediante hashing y, con números primos enormes, en el cifrado RSA que protege las comunicaciones en internet.

Aritmética modular
Sistema de restos y sus operaciones; el cálculo del reloj.

# Aritmética modular
## Idea
### reloj de m casillas
### restos del cero a m menos uno
## Operar
### sumar y multiplicar reduciendo
### exponenciación modular
## Usos
### hashing
### checksums
### criptografía RSA

Algoritmo de Euclides
Halla el máximo común divisor y permite construir inversos modulares.