Aritmética modular es una forma simple de realizar aritmética en un conjunto finito de enteros.

Sea a, r, m ∈ Z (donde Z es un conjunto de todos los enteros) y m > 0 . Se escribe:

si m divide a - r.

Donde:

• m es llamado el módulo
• r es llamado el residuo

La línea a ≡ r mod m se lee como "a es congruente con r módulo m"

Se supone que se divide a y r por m, obteniendo cocientes y residuos enteros, donde los residuos están entre 0 y m - 1. Es decir, a = q₁m + r₁ y r = q₂m + r₂, donde 0 < r₁ < m-1 y 0 < r₂ < m-1.

Entonces no es difícil ver que a ≡ r mod m si y solo si r₁ = r₂.

OBSERVACIÓN: Para propósito de la criptografía siempre se define a mod m como un número no-negativo.

Ahora se puede definir el módulo aritmético m: Z_m se define como el conjunto {0 , ... , m-1}, equipado con dos operaciones, + y *. La suma y la multiplicación modular son exactamente como la suma y multiplicación aritmética, excepto que los resultados se reducen módulo m.

Por ejemplo, supongamos que queremos calcular 11 × 13 en Z₁₆. Como números enteros, tenemos 11 × 13 = 143. Para reducir 143 módulo 16, simplemente realizamos una división larga ordinaria: 143 = 8 × 16 + 15, por lo que 143 mod 16 = 15 y, por lo tanto, 11 × 13 = 15 en Z₁₆.

---

Referencias

1. Christof Paar, Jan Pelzl. (2010). Understanding Cryptography. Berlin Heidelberg: Springer.
2. Douglas Stinson. (1995). Cryptography: Theory and Practice. United States: CRC Press.