Chinese Remainder Theorem
Teorema chino del resto: si los módulos son coprimos por pares, un sistema de congruencias tiene una solución única módulo su producto.
Propósito
Descomponer la aritmética de módulo grande en aritmética paralela de módulos pequeños, acelerando el cálculo modular de números grandes.
Mecanismo
Dado x≡a_i (mod n_i) con los n_i coprimos por pares, x tiene una solución única mod N (N=∏n_i). Use N_i=N/n_i, M_i=N_i^(-1) mod n_i, y x=∑a_i*N_i*M_i mod N.
Casos de uso
- Aceleración de RSA
- Aritmética modular de números grandes
- Algoritmos de teoría de números