Teorema chino del resto

El teorema chino del resto es un resultado sobre congruencias en teoría de números y sus generalizaciones en álgebra abstracta. El enunciado dice:

Sean $n,m \in \mathbb{N}$ tales que $\operatorname{mcd}(n, m) = 1 \,$ (primos relativos). Entonces dados cualesquiera $b_1,b_2 \in \mathbb{Z}$, existe un $x \in \mathbb{Z}$ tal que: $x \equiv b_1 \pmod n$ y $x \equiv b_2 \pmod m$ Y además, si existen otros $v,w \in \mathbb{Z}$ que satisfagan las dos congruencias anteriores entonces: $v \equiv w \pmod {n \cdot m}$

Enunciado del teorema

La forma original del teorema, contenida en un libro del siglo III por el matemático chino Sun Tzu [1] y posteriormente publicado en 1247 por Qin Jiushao, es un enunciado sobre congruencias simultáneas (ver aritmética modular).

Supongamos que n₁, n₂, …, n_k son enteros coprimos dos a dos. Entonces, para enteros dados a₁,a₂, …, a_k, existe un entero x que resuelve el sistema de congruencias simultáneas

$\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align}$

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto N = n₁n₂...n_k.

Algunas veces, las congruencias simultáneas pueden ser resueltas aun si los n_i's no son coprimos a pares. Una solución x existe si y sólo si:

$a_i \equiv a_j \pmod{\operatorname{mcd}(n_i,n_j)} \qquad \mbox{para todo }i\mbox{ y }j . \,\!$

Todas las soluciones x son entonces congruentes módulo el mínimo común múltiplo de los n_i.

Versiones del teorema chino del resto fueron también conocidas por Brahmagupta, y aparecen en el Liber Abaci de Fibonacci (1202).

Aplicaciones

El teorema chino del resto tiene importantes aplicaciones en criptografía, en especial para reducir operaciones con números enormes mediante el paso a congruencias. En el algoritmo RSA, por ejemplo, los cálculos se hacen módulo n, donde n es un producto de dos primos p y q. Tamaños habituales para n son 1024, 2048 ó 4096 bits, haciendo que los cálculos requieran una gran cantidad de tiempo. Usando el teorema chino del resto los cálculos pueden ser transportados del anillo $\Bbb{Z}_n$ al anillo $\Bbb{Z}_p \times \Bbb{Z}_q$. La suma de las longitudes de bit de p y q es la longitud de bit de n, haciendo p y q considerablemente menor que n. Esto acelera mucho los cálculos. Nótese que las implementaciones del algoritmo RSA usando el teorema chino del resto son más susceptibles a ataques de "fault injection".

Referencias

• Koblitz, Neal (1998). A Course in Number Theory and Cryptography (2ª edición). EE. UU.: Springer. pp. 238. ISBN 978-0-387-94293-3.