Modular Arithmetic
La aritmética modular toma restos tras operaciones enteras, manteniendo los resultados en [0, n); es el fundamento de la teoría de números y la criptografía.
Propósito
Mantener las operaciones cerradas en un rango finito, base de RSA, Diffie-Hellman y otras técnicas criptográficas.
Mecanismo
(a + b) mod n y (a × b) mod n se definen bajo módulo n. El inverso modular a^(-1) satisface a·a^(-1) ≡ 1 (mod n); existe cuando gcd(a,n)=1 y se halla con el algoritmo extendido de Euclides. Por el pequeño teorema de Fermat, a^(p-1) ≡ 1 (mod p) para p primo.
Casos de uso
- Cifrado y descifrado con RSA
- Intercambio de claves Diffie-Hellman
- Sharding por hash y módulo
- Cálculo de checksums
Ejemplos
- entrada
(7 + 8) mod 5Output015 mod 5 = 0
Errores comunes
- Negative modulo behaves differently across languages
- Know your language's behavior or normalize with ((a%n)+n)%n
Términos relacionados
BigInteger
BigInteger es un tipo de entero de precisión arbitraria, no limitado por un tamaño de palabra fijo, usado para cálculos más allá del rango de los enteros nativos (como criptografía y combinatoria). GLOSARIO
Prime Number
Un número primo es un número natural mayor que 1 divisible solo entre 1 y sí mismo; es el bloque constituyente de la teoría de números, y todo entero se factoriza de forma única en primos. GLOSARIO
GCD
El MCD (máximo común divisor) es el mayor entero positivo que divide a dos o más enteros, calculado eficientemente con el algoritmo de Euclides. GLOSARIO