16.7: Una aplicación para el diseño de software

El Teorema del resto chino es un resultado de la teoría elemental de números sobre la solución de sistemas de congruencias simultáneas. El matemático chino Sun-tsï escribió sobre el teorema en el siglo I d.C. Este teorema tiene algunas consecuencias interesantes en el diseño de software para procesadores paralelos.

Lema\(16.41\)

Dejar\(m\) y\(n\) ser enteros positivos tal que\(\gcd( m, n) = 1\text{.}\) Entonces para\(a, b \in {\mathbb Z}\) el sistema

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

tiene una solución. Si\(x_1\) y\(x_2\) son dos soluciones del sistema, entonces\(x_1 \equiv x_2 \pmod{mn}\text{.}\)

Prueba

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

\[ a + k_1 m \equiv b \pmod{n}\text{.} \nonumber \]

Esto equivale a demostrar que

\[ k_1 m \equiv (b-a) \pmod{n} \nonumber \]

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

\[ (b-a) ms = (b-a) -(b-a) nt\text{,} \nonumber \]

o

\[ [(b-a)s]m \equiv (b-a) \pmod{n}\text{.} \nonumber \]

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

Para demostrar que cualesquiera dos soluciones son congruentes módulo\(mn\text{,}\) let\(c_1\) y\(c_2\) ser 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{.}\) Then

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

Por lo tanto, ambos\(m\) y\(n\) dividir\(c_1 - c_2\text{.}\) En consecuencia,\(c_2 \equiv c_1 \pmod{mn}\text{.}\)

Ejemplo\(16.42\)

Vamos a resolver el sistema

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

Solución

Usando el algoritmo euclidiano, podemos encontrar enteros\(s\) y\(t\) tal que\(4s + 5t = 1\text{.}\) Dos de tales enteros son\(s = 4\) y\(t = -3\text{.}\) Consecuentemente,

\[ x = a + k_1 m = 3 + 4k_1 = 3 + 4[(5 - 4)4] = 19\text{.} \nonumber \]

Teorema\(16.43\). Chinese Remainder Theorem

Dejar\(n_1, n_2, \ldots, n_k\) ser enteros positivos tal que\(\gcd(n_i, n_j) = 1\) para\(i \neq j\text{.}\) Entonces para cualquier número entero\(a_1, \ldots, a_k\text{,}\) el sistema

\ 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*}

tiene una solución. Además, dos soluciones cualesquiera del sistema son congruentes módulo\(n_1 n_2 \cdots n_k\text{.}\)

Prueba

Utilizaremos la inducción matemática sobre el número de ecuaciones en el sistema. Si hay\(k= 2\) ecuaciones, entonces el teorema es cierto por Lema\(16.41\). Ahora supongamos que el resultado es cierto para un sistema de\(k\) ecuaciones o menos y que deseamos encontrar una solución de

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

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

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

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

Ejemplo\(16.44\)

Vamos a resolver el sistema

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

Solución

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

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

Resolviendo las siguientes dos ecuaciones, podemos reducir el sistema a

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

Resolviendo este último sistema, encontramos que\(19\) es una solución para el sistema que es única hasta módulo\(1260\text{.}\)

Una aplicación interesante del Teorema del resto chino en el diseño de programas informáticos es que el teorema nos permite dividir un cálculo que involucra grandes enteros en varios cálculos menos formidables. Una computadora manejará cálculos enteros solo hasta cierto tamaño debido al tamaño de su chip de procesador, que suele ser un chip de procesador de 32 o 64 bits. Por ejemplo, el número entero más grande disponible en una computadora con un chip de procesador de 64 bits es

\[ 2^{63} - 1 = 9{,}223{,}372{,}036{,}854{,}775{,}807\text{.} \nonumber \]

Se han propuesto o están en desarrollo procesadores más grandes como 128 o 256 bits. Incluso se habla de un chip de procesador de 512bits. El entero más grande con el que podría almacenar dicho chip sería el\(2^{511} - 1\text{,}\) que sería un número de 154 dígitos. Sin embargo, tendríamos que lidiar con números mucho más grandes para romper esquemas de cifrado sofisticados.

Se requiere un software especial para los cálculos que involucran números enteros más grandes que no pueden ser agregados directamente por la máquina. Al usar el Teorema del resto chino podemos descomponer grandes adiciones y multiplicaciones de enteros en cálculos que la computadora puede manejar directamente. Esto es especialmente útil en computadoras de procesamiento paralelo que tienen la capacidad de ejecutar varios programas simultáneamente.

La mayoría de las computadoras tienen una sola unidad central de procesamiento (CPU) que contiene un chip de procesador y solo pueden agregar dos números a la vez. Para agregar una lista de diez números, la CPU debe hacer nueve adiciones en secuencia. Sin embargo, una computadora de procesamiento paralelo tiene más de una CPU. Una computadora con 10 CPU, por ejemplo, puede realizar 10 adiciones diferentes al mismo tiempo. Si podemos tomar un entero grande y descomponerlo en partes, enviando cada parte a una CPU diferente, entonces realizando varias adiciones o multiplicaciones simultáneamente en esas partes, podemos trabajar con un entero que la computadora no sería capaz de manejar como un todo.

Ejemplo\(16.45\)

Supongamos que deseamos multiplicar\(2134\) por\(1531\text{.}\)

Solución

Usaremos los enteros\(95\text{,}\)\(97\text{,}\)\(98\text{,}\) y\(99\) porque son relativamente primos. Podemos dividir cada entero 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}\ text {.} \ end {alinear*}

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 punto 1531 &\ equiv 55\ cdot 46\ equiv 55\ pmod {99}\ texto {.} \ end {alinear*}

Cada uno de estos cuatro cómputos se puede enviar a un procesador diferente si nuestro equipo tiene varias CPU. Por el cálculo anterior, sabemos que\(2134 \cdot 1531\) es una solución del sistema

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

El teorema del resto chino nos dice que las soluciones son únicas hasta módulo\(95 \cdot 97 \cdot 98 \cdot 99 = 89{,}403{,}930\text{.}\) Resolver este sistema de congruencias para nos\(x\) dice que\(2134 \cdot 1531 = 3{,}267{,}154\text{.}\)

La conversión del cómputo en los cuatro subcómputos llevará algún tiempo de cómputos. Además, resolver el sistema de congruencias también puede llevar un tiempo considerable. Sin embargo, si tenemos muchos cómputos a realizar en un determinado conjunto de números, tiene sentido transformar el problema como lo hemos hecho anteriormente y realizar los cálculos necesarios simultáneamente.