Ir ao conteúdo principal

Seção 16.5 Una Aplicación al Diseño de Software

El Teorema Chino de los Restos es un resultado de teoría elemental de números sobre las soluciones simultáneas de sistemas de congruencias. El matemático chino Sun-tsï escribió sobre este teorema en el siglo primero D.C. Este teorema tiene interesantes consecuencias en el diseño de software para el uso de procesadores en paralelo.

La ecuación \(x \equiv a \pmod{m}\) tiene solución pues \(a + km\) satisface la ecuación para todo \(k \in {\mathbb Z}\text{.}\) Debemos mostrar que existe un entero \(k_1\) tal que

\begin{equation*} a + k_1 m \equiv b \pmod{n}. \end{equation*}

Esto es equivalente a mostrar que

\begin{equation*} k_1 m \equiv (b-a) \pmod{n} \end{equation*}

tiene solución para \(k_1\text{.}\) Como \(m\) y \(n\) son relativamente primos, existen enteros \(s\) y \(t\) tales que \(ms + nt = 1\text{.}\) Concluimos que,

\begin{equation*} (b-a) ms = (b-a) -(b-a) nt, \end{equation*}

o

\begin{equation*} [(b-a)s]m \equiv (b-a) \pmod{n}. \end{equation*}

Ahora sea \(k_1 = (b-a)s\text{.}\)

Para mostrar que dos soluciones cualquiera son congruentes módulo \(mn\text{,}\) sean \(c_1\) y \(c_2\) dos soluciones del sistema. Es decir,

\begin{align*} c_i & \equiv a \pmod{m}\\ c_i & \equiv b \pmod{n} \end{align*}

para \(i = 1, 2\text{.}\) Entonces

\begin{align*} c_2 & \equiv c_1 \pmod{m}\\ c_2 & \equiv c_1 \pmod{n}. \end{align*}

por lo tanto, tanto \(m\) como \(n\) dividen a \(c_1 - c_2\text{.}\) Concluimos que \(c_2 \equiv c_1 \pmod{mn}\text{.}\)

Resolvamos el sistema

\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}. \end{align*}

Usando el algoritmo de Euclides, podemos encontrar enteros \(s\) y \(t\) tales que \(4s + 5t = 1\text{.}\) Una posibilidad para tales enteros es \(s = 4\) y \(t = -3\text{.}\) Concluimos que

\begin{equation*} x = a + k_1 m = 3 + 4k_1 = 3 + 4[(5 - 4)4] = 19. \end{equation*}

Procederemos por inducción en el número de ecuaciones en el sistema. Si hay \(k= 2\) ecuaciones, entonces el teorema es cierto por el Lema 16.5.1. Ahora supongamos que el resultado es verdadero para un sistema de \(k\) o menos ecuaciones y que deseamos encontrar una solución de

\begin{align*} x & \equiv a_1 \pmod{n_1}\\ x & \equiv a_2 \pmod{n_2}\\ & \vdots \\ x & \equiv a_{k+1} \pmod{n_{k+1}}. \end{align*}

Considerando las primeras \(k\) ecuaciones, existe una solución que es única módulo \(n_1 \cdots n_k\text{,}\) digamos \(a\text{.}\) Como \(n_1 \cdots n_k\) y \(n_{k+1}\) son relativamente primos, el sistema

\begin{align*} x & \equiv a \pmod{n_1 \cdots n_k }\\ x & \equiv a_{k+1} \pmod{n_{k+1}} \end{align*}

tiene una solución que es única módulo \(n_1 \ldots n_{k+1}\) por el lema.

Resolvamos el sistema

\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}. \end{align*}

Del Ejemplo 16.5.2 sabemos que 19 es una solución de las primeras dos congruencias y cualquier otra solución del sistema es congruente a \(19 \pmod{20}\text{.}\) Luego, podemos reducir el sistema a un sistema de tres congruencias:

\begin{align*} x & \equiv 19 \pmod{20}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}. \end{align*}

Resolviendo las siguientes dos ecuaciones, podemos reducir el sistema a

\begin{align*} x & \equiv 19 \pmod{180}\\ x & \equiv 5 \pmod{7}. \end{align*}

Resolviendo este último sistema, encontramos que 19 es una solución para el sistema que es única módulo 1260.

Una aplicación interesante del Teorema Chino de los Restos en el diseño de software computacional es que el teorema nos permite descomponer un cálculo que involucre enteros grandes en varios cálculos menos grandes. Un computador puede trabajar con enteros solamente hasta cierto tamaños debido al tamaño de su procesador, que usualmente es un procesador de 32 o 64-bit. Por ejemplo, el mayor entero disponible en un computador con un procesador de 64-bit es

\begin{equation*} 2^{63} - 1 = \text{9,223,372,036,854,775,807}. \end{equation*}

Procesadores mayores como 128 o 256-bit han sido propuesto o están en desarrollo. Incluso se habla de un procesador de 512-bit. El mayor entero que tal procesador podría almacenar sería \(2^{511} - 1\text{,}\) que es un número de 154 dígitos. Sin embargo, necesitaríamos trabajar con números mucho más grandes para romper sofisticados métodos de encriptación.

Se requiere software especial para cálculos con enteros mayores que no pueden ser sumados directamente por la máquina. Usando el Teorema Chino de los Restos podemos descomponer sumas y multiplicaciones de enteros grandes en cálculos que el computador pueda hacer de forma directa. Esto es especialmente útil para el procesamiento paralelo.

La mayor parte de los computadores tiene una única unidad central de proceso (CPU) que contiene un chip procesador que puede sumar solo dos números a la vez. Para sumar una lista de diez números, la CPU debe hacer nueve sumas sucesivamente. Sin embargo un computador de procesamiento paralelo tiene más de una CPU. Un computador con 10 CPUs, por ejemplo, puede hacer 10 operaciones diferentes al mismo tiempo. Si podemos tomar un entero grande y descomponerlo en sus partes, enviando cada una de las partes a una CPU diferente, entonces haciendo sumas y multiplicaciones en paralelo, podemos trabajar con enteros con los que el computador no podría trabajar directamente.

Supongamos que deseamos multiplicar 2134 por 1531. Usaremos los enteros 95, 97, 98, y 99 pues estos son relativamente primos. Descomponemos cada uno de los enteros en cuatro partes:

\begin{align*} 2134 & \equiv 44 \pmod{95}\\ 2134 & \equiv 0 \pmod{97}\\ 2134 & \equiv 76 \pmod{98}\\ 2134 & \equiv 55 \pmod{99} \end{align*}

y

\begin{align*} 1531 & \equiv 11 \pmod{95}\\ 1531 & \equiv 76 \pmod{97}\\ 1531 & \equiv 61 \pmod{98}\\ 1531 & \equiv 46 \pmod{99}. \end{align*}

Multiplicando las ecuaciones correspondientes, obtenemos

\begin{align*} 2134 \cdot 1531 & \equiv 44 \cdot 11 \equiv 9 \pmod{95}\\ 2134 \cdot 1531 & \equiv 0 \cdot 76 \equiv 0 \pmod{97}\\ 2134 \cdot 1531 & \equiv 76 \cdot 61 \equiv 30 \pmod{98}\\ 2134 \cdot 1531 & \equiv 55 \cdot 46 \equiv 55 \pmod{99}. \end{align*}

Cada uno de estos cálculos puede ser enviado a un procesador diferente si nuestro computador tiene varias CPU. Por el cálculo anterior, sabemos que \(2134 \cdot 1531\) es una solución de este sistema

\begin{align*} x & \equiv 9 \pmod{95}\\ x & \equiv 0 \pmod{97}\\ x & \equiv 30 \pmod{98}\\ x & \equiv 55 \pmod{99}. \end{align*}

El Teorema Chino de los Restos que la solución es única módulo \(95 \cdot 97 \cdot 98 \cdot 99 = \text{89,403,930}\text{.}\) Resolviendo el sistema para \(x\) nos dice que \(2134 \cdot 1531 = \text{3,267,154}\text{.}\)

La conversión del cálculo en sus cuatro componentes tomará cierto tiempo de cálculo. Además, resolver el sistema de congruencias puede tomar un tiempo considerable. A pesar de ello, si tenemos muchos cálculos que realizar en un conjunto particular de números, tiene sentido transformar el problema como hicimos arriba y hacer los cálculos necesarios de forma simultánea.

Sage.

Los Anillos están en el núcleo del diseño de Sage por lo que encontraremos una gran variedad de posibilidades para calcular con anillos y con cuerpos. Ideales, cocientes, y homomorfismos están todos disponibles.