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 Zi​​ 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{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}$

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto $N=n_{1}n_{2}...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 ${\mathbb {Z}}_{n}$ al anillo ${\mathbb {Z}}_{p}\times {\mathbb {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".

Anécdota

Hay una vetusta chirigota, viajera de siglos, cuya paternidad le otorgan a Sun Zi (s. I), que dice así: «Halle dos números enteros positivos mínimos que posean residuos 2, 3, 2 si se dividen entre 3, 5, 7, respectivamente». Procesando se hallan los dos números positivos mínimos 23 y 128. Resuelva para 3, luego para 5; en seguida para 15, y, por último, para 3.5.7. Esto funciona si los módulos sucesivos son primos entre sí.​

Referencias

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