Teorema chino del resto

Teorema chino del resto

De Wikipedia, la enciclopedia libre

Sean n,m \in \mathbb{N}-\{0\} tales que mcd(n, m) = 1 \, (primos relativos).

Entonces dados cualesquiera b_1,b_2 \in \mathbb{Z}, \exists x \in \mathbb{Z} tal que:

x \equiv b_1{\ }(mod \ n) y x \equiv b_2{\ }(mod \ m)

Y además si existen otros v,w \in \mathbb{Z} que satisfagan las dos congruencias anteriores entonces:

v \equiv w{\ }(mod {\ }n{\cdot}m)

[editar] 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 n1, n2, …, nk son enteros coprimos de a pares. Entonces, para enteros dados a1,a2, …, ak, 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 = n1n2...nk.

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

a_i \equiv a_j \pmod{\gcd(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 ni.

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


[editar] Aplicaciones

Tiene aplicaciones en: Criptografía

En el algoritmo RSA 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. 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".


Icono de esbozo
 El contenido de esta página es un esbozo sobre matemática. Ampliándolo ayudarás a mejorar Wikipedia.
Puedes ayudarte con las wikipedias en otras lenguas.
El contenido de esta página (o parte de ella) fue extraído de wikipedia y puede redistribuirse libremente bajo la licencia de documentación libre GNU