Teorema Chino De Los Restos Crt

Teorema Chino de los Restos (CRT) – Explicación y aplicación en programación

El Teorema Chino de los Restos es una herramienta poderosa en aritmética modular, que permite resolver sistemas de congruencias simultáneas de forma eficiente. Tiene aplicaciones directas en criptografía (RSA), optimización de cálculos, programación paralela, sistemas distribuidos, sincronización y teoría de números computacional.

Relacionado: Pequeno-Teorema-de-Fermat, Congruencias, Criptografía AES.

¿Qué dice el Teorema Chino de los Restos?

Dado un sistema de congruencias:

x \equiv a 1 m o d m 1 x \equiv a 2 m o d m 2 ⋮ x \equiv akm o d mk ⎩ ⎨ ⎧ x \equiv a_{1} mod m_{1} x \equiv a_{2} mod m_{2} ⋮ x \equiv a_{k} mod m_{k}

Si los módulos $m 1, m 2, ..., mk m_{1}, m_{2}, ..., m_{k}$ son pares mutuamente coprimos (es decir, $gcd⁡(mi,mj)=1$$$$\gcd(m_i, m_j) = 1$ para $i \neq = ji \neq = j$ , entonces existe una única solución módulo $M = m 1 \cdot m 2 \dots mk M = m_{1} \cdot m_{2} \dots m_{k} .$

¿Qué significa?

Puedes encontrar un solo número x tal que cumple todas las congruencias del sistema, y además:

x m o d M es u ˊ ni c a x mod M es \overset{u}{ˊ} nica

️ En programación: ¿para qué sirve?

1. Criptografía: RSA optimizado

En RSA, la operación de descifrado puede acelerarse usando CRT:

En lugar de calcular $c d m o d n c^{d} mod n$ con un n grande,
Se calcula con pp y qq (factores de n), más pequeños:

m1 = c^d mod p
m2 = c^d mod q

Luego se usa CRT para recomponer el resultado final.

️ 2. Sincronización de ciclos

Ejemplo:

Tren A pasa cada 3 minutos, tren B cada 5 minutos.
¿Cuándo coinciden ambos otra vez?
→ Resolver:

x≡0mod  3x≡0mod  5⇒x≡0mod  15x \equiv 0 $$ $$\mod 3 \\ x \equiv 0 \mod 5 \Rightarrow x \equiv 0 \mod 15

3. Optimización de grandes cálculos

En cálculos con enteros enormes, se pueden hacer módulos más pequeños en paralelo (residuos), y luego recomponer el resultado final con CRT.

️ Esto se usa en:

Procesadores RNS (Residue Number Systems).
Sistemas distribuidos.
Compresión y cifrado.

Cómo resolverlo en la práctica

Supongamos:

x \equiv 2 m o d 3 x \equiv 3 m o d 4 x \equiv 1 m o d 5 x \equiv 2 mod 3 x \equiv 3 mod 4 x \equiv 1 mod 5

Paso 1: Calcular el producto total M=3⋅4⋅5=60M = 3 \cdot 4 \cdot 5 = 60

Paso 2: Para cada congruencia:

- Mi=M/miM_i = M / m_i $$ - yi=Mi−1mod  miy_i = M_i^{-1} \mod m_i $$ - Sumar: x=∑ai⋅Mi⋅yimod  Mx = \sum a_i \cdot M_i \cdot y_i \mod M

Ejemplo en Python

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x1, y1 = extended_gcd(b, a % b)
    return d, y1, x1 - (a // b) * y1
 
def modinv(a, m):
    d, x, _ = extended_gcd(a, m)
    if d != 1:
        raise ValueError("No hay inverso")
    return x % m
 
def crt(congruencias):
    M = 1
    for _, m in congruencias:
        M *= m
 
    x = 0
    for a_i, m_i in congruencias:
        M_i = M // m_i
        y_i = modinv(M_i, m_i)
        x += a_i * M_i * y_i
 
    return x % M

Uso:

congs = [(2, 3), (3, 4), (1, 5)]
print("Solución CRT:", crt(congs))  # → 11

️ Verificación:

11mod 3=211 \mod 3 = 2
11mod 4=311 \mod 4 = 3
11mod 5=111 \mod 5 = 1

Conclusión

El Teorema Chino de los Restos es una joya de la teoría de números que se aplica directamente en programación avanzada, sobre todo cuando se requiere:

trabajar con módulos distintos simultáneamente,
acelerar cálculos grandes dividiendo en partes pequeñas,
mantener exactitud con enteros grandes,
o combinar soluciones congruentes en criptografía, redes o sistemas distribuidos.

¿Quieres que te prepare un ejemplo con RSA donde se use el CRT para descifrar más rápido, o una visualización paso a paso de cómo se recombinan las congruencias en Python?

Quartz 4

Explorer