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. Fue publicado por primera vez en el siglo III por el matemático chino Sun Tzu.

Enunciado del teorema

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

${\displaystyle {\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 ${\displaystyle N=n_{1}n_{2}...n_{k}}$ .

De manera más general, las congruencias simultáneas pueden ser resueltas si los n_i's son coprimos a pares. Una solución x existe si y solo si:

${\displaystyle a_{i}\equiv a_{j}{\pmod {\operatorname {mcd} (n_{i},n_{j})}}\qquad {\text{para todo }}i\ {\text{y }}j.\,\!}$ 

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

Un enunciado moderno en lenguaje algebraico es que para cada entero positivo con factorización en números primos

${\displaystyle n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}},}$ 

se tiene un isomorfismo entre un anillo y la suma directa de sus potencias primas^[1]​

${\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /p_{1}^{r_{1}}\mathbb {Z} \oplus \cdots \oplus \mathbb {Z} /p_{k}^{r_{k}}\mathbb {Z} .}$ 

Demostración del teorema

Existencia de la solución

Sea N=n₁n₂...n_k y sea ${\displaystyle N_{i}={\frac {N}{n_{i}}}}$  para i=1,...,k. Como todos los módulos n_i son coprimos entre sí, N_i y n_i son a su vez coprimos entre sí, luego por la Identidad de Bezout se asegura la existencia de dos enteros r_i y s_i tales que ${\displaystyle r_{i}n_{i}+s_{i}N_{i}=1}$ . En tales condiciones, tomando las clases de equivalencia en ambos lados de la identidad, se tiene que para cada i, y para cada j ≠ i:

${\displaystyle {\begin{aligned}s_{i}N_{i}\equiv 1{\pmod {n_{i}}}\\s_{i}N_{i}\equiv 0{\pmod {n_{j}}}\\\end{aligned}}}$ 

Por tanto, definiendo

${\displaystyle x:=\sum _{i=1}^{k}a_{i}s_{i}N_{i}=a_{1}s_{1}N_{1}+a_{2}s_{2}N_{2}+\ldots +a_{k}s_{k}N_{k},}$ 

es claro que x es la solución buscada, debido a que al tomar clases de equivalencia en cada n_i, todos los sumandos se anulan a excepción del propio a_is_iN_i, y por tanto, ${\displaystyle x\equiv a_{i}{\pmod {n_{i}}}}$  para todo i =1,...,k. De esta manera, queda demostrado que x es solución del sistema.

Unicidad de la solución

En el caso de que todos los n_i sean coprimos, esa solución es la única existente módulo N. Para demostrarlo, supongamos que existiesen dos números enteros x e y que son soluciones distintas, entonces para i =1,2,...,k:

${\displaystyle {\begin{aligned}x\equiv a_{i}{\pmod {n_{i}}}\\y\equiv a_{i}{\pmod {n_{i}}}\\\end{aligned}}}$ 

Esto implica que ${\displaystyle x-y\equiv 0{\pmod {n_{i}}}}$ , y por ser todos los n_i coprimos, se sigue que el producto de los módulos N=n₁n₂...n_k también divide a x - y, es decir, ${\displaystyle x\equiv y{\pmod {N}}}$ .

Por tanto, toda solución del sistema es congruente con x en módulo N, tal y como se había establecido previamente en la formulación del teorema.

Historia

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

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

Aplicaciones en criptografía

El teorema del resto chino 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 ${\displaystyle n}$ , donde ${\displaystyle n}$  es un producto de dos primos ${\displaystyle p}$  y ${\displaystyle q}$ . Tamaños habituales para ${\displaystyle n}$  son 1024, 2048 o 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 ${\displaystyle \mathbf {Z} _{n}}$  al anillo ${\displaystyle \mathbf {Z} _{p}\times \mathbf {Z} _{q}}$ . La suma de las longitudes de bit de ${\displaystyle p}$  y ${\displaystyle q}$  es la longitud de bit de ${\displaystyle n}$ , haciendo ${\displaystyle p}$  y ${\displaystyle q}$  considerablemente menor que ${\displaystyle 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".

Notas

1. Ireland y Rosen, 1990
2. «Truth and Lies. Mapping the most complex known mathematical object». Higher Mathematics (en inglés). The Economist. 22 de marzo de 2007. Consultado el 26 de diciembre de 2011. «This theorem is contained in a book written in the late third-century AD by a mathematician called Sun Tzu (not to be confused with the military strategist of the same name). It is used to simplify large calculations by breaking them down into many smaller ones, the results of which can then be recombined to generate the answer to the original question. » 
3. Ribnikov, Historia de las matemáticas, p. 42.

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. 
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd edición), Springer-Verlag, ISBN 0-387-97329-X .

Enlaces externos

• Weisstein, Eric W. .html «Chinese Remainder Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

•   Datos: Q193878