Teorema chino del resto

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 n1, n2, …, nk son enteros coprimos dos a dos. 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{\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 ni.

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. 

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Teorema de congruencia lineal — En aritmética modular, la cuestión de cuándo una congruencia lineal puede ser resuelta se describe mediante el teorema de congruencia lineal. Si a y b dos números enteros cualesquiera y n es un número entero positivo, entonces la congruencia (1)… …   Wikipedia Español

  • Aritmética modular — Saltar a navegación, búsqueda Cubierta de la edición original de Disquisitiones arithmeticae de Gauss, libro fundamental de la aritmética modular. En matemática, la aritmética modular es un sistema aritmético para clases de equivalencia((Clase de …   Wikipedia Español

  • Disquisitiones arithmeticae — Saltar a navegación, búsqueda Página del título en la primera edición Disquisitiones Arithmeticae es un libro de teoría de números escrito por el matemático alemán Carl Friedrich Gauss en 1798 cuando tenía 21 a …   Wikipedia Español

  • Teoría de números — Nuestra teoría de números se deriva de la antigua aritmética griega de Diofanto.[1] Portada de la aritmética de Diofanto traducida al latín por Bachet de Méziriac, edición con comentarios de Pierre de Fermat publicada en 1670 …   Wikipedia Español

  • Función de Carmichael — En Teoría de números, la función de Carmichael de un entero positivo n, denotada λ(n), se define como el menor entero m tal que cumple: para cada número entero a coprimo con n. En otras palabras, define el exponente del grupo multiplicativo de… …   Wikipedia Español

  • RSA — En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente. La seguridad de… …   Wikipedia Español

  • Qin Jiushao — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar al autor p …   Wikipedia Español

  • Ideal (teoría de anillos) — En matemáticas, un ideal es una estructura algebraica definida en un anillo. Los ideales generalizan de manera fecunda el estudio de la divisibilidad en los números enteros. De este modo, es posible enunciar versiones muy generales de teoremas… …   Wikipedia Español

  • Función beta de Gödel — En lógica matemática, la función beta de Gödel es una función numérica que permite la definición de funciones recursivas dentro de una teoría formal aritmética. Definición y propiedades La definición de la función beta es la siguiente: Dados tres …   Wikipedia Español

  • Cribado grande — De la manera más facil y sencilla Cribar es Cernir, colar, filtrar, tamizar, depurar; se usa en otras áreas como una expresión para indicar: seleccionar, separar, escoger, diferenciar o elegir algo de entre mucho. Por ejemplo en medicina, para… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”