Teorema chino del resto

Supongamos que x e y son soluciones de todas las congruencias. Como x e y dan el mismo resto, al dividirlos por n _i , su diferencia x − y es un múltiplo de cada n _i . Como los n _i son coprimos dos a dos, su producto N también divide a x − y , y por lo tanto x e y son congruentes módulo N . Si se supone que x e y son no negativos y menores que N (como en el primer enunciado del teorema), entonces su diferencia puede ser un múltiplo de N solo si x = y .

El mapa

${\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots,x{\bmod {n}}_{k})}$

Esta función mapea clases de congruencia módulo N a secuencias de clases de congruencia módulo n _i . La prueba de unicidad demuestra que esta función es inyectiva . Como el dominio y el codominio de esta función tienen el mismo número de elementos, también es sobreyectiva , lo que demuestra la existencia de la solución.

Esta demostración es muy sencilla, pero no proporciona un método directo para calcular la solución. Además, no se puede generalizar a otras situaciones, a diferencia de la siguiente demostración.

La existencia puede establecerse mediante una construcción explícita de x . ^{[ 16 ]} Esta construcción puede dividirse en dos pasos, primero resolviendo el problema en el caso de dos módulos y luego extendiendo esta solución al caso general por inducción sobre el número de módulos.

Para construir una solución, no es necesario realizar una inducción sobre el número de módulos. Sin embargo, esta construcción directa implica más cálculos con números grandes, lo que la hace menos eficiente y menos utilizada. No obstante, la interpolación de Lagrange es un caso particular de esta construcción, aplicada a polinomios en lugar de números enteros.

Dejar${\displaystyle N_{i}=N/n_{i}}$ser el producto de todos los módulos menos uno. Como el${\displaystyle n_{i}}$son coprimos por pares,${\displaystyle N_{i}}$y${\displaystyle n_{i}}$son coprimos. Por lo tanto, se aplica la identidad de Bézout y existen enteros${\displaystyle M_{i}}$y${\displaystyle m_{i}}$de tal manera que

${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1.}$

Una solución del sistema de congruencias es

${\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.}$

De hecho, como${\displaystyle N_{j}}$es un múltiplo de${\displaystyle n_{i}}$para${\displaystyle i\neq j,}$ tenemos

${\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}$

por cada${\displaystyle i.}$

Es fácil comprobar si un valor de x es una solución: basta con calcular el resto de la división euclidiana de x entre cada n _i . Por lo tanto, para encontrar la solución, basta con comprobar sucesivamente los enteros desde 0 hasta N hasta dar con ella.

Aunque muy simple, este método es muy ineficiente. Para el ejemplo sencillo que se considera aquí, hay que comprobar 40 números enteros (incluido el 0 ) para encontrar la solución, que es 39. Este es un algoritmo de tiempo exponencial , ya que el tamaño de la entrada es, salvo un factor constante, el número de dígitos de N , y el número medio de operaciones es del orden de N.

Por lo tanto, este método se usa raramente, ni para cálculos manuales ni en ordenadores.

La búsqueda de la solución puede hacerse mucho más rápida mediante el tamizado. Para este método, suponemos, sin pérdida de generalidad , que${\displaystyle 0\leq a_{i}<n_{i}}$(si no fuera así, bastaría con reemplazar cada uno${\displaystyle a_{i}}$por el resto de su división por${\displaystyle n_{i}}$Esto implica que la solución pertenece a la progresión aritmética.

${\displaystyle a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots }$

Al probar los valores de estos números módulo${\displaystyle n_{2},}$Al final uno encuentra una solución.${\displaystyle x_{2}}$de las dos primeras congruencias. Entonces la solución pertenece a la progresión aritmética.

${\displaystyle x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots }$

Probando los valores de estos números módulo${\displaystyle n_{3},}$y continuando hasta que se hayan probado todos los módulos, finalmente se obtiene la solución.

Este método es más rápido si los módulos se han ordenado por valor decreciente, es decir, si${\displaystyle n_{1}>n_{2}>\cdots >n_{k}.}$Por ejemplo, esto da como resultado el siguiente cálculo. Primero consideramos los números congruentes con 4 módulo 5 (el módulo más grande), que son 4, 9 = 4 + 5 , 14 = 9 + 5 , ... Para cada uno de ellos, calculamos el resto de la división por 4 (el segundo módulo más grande) hasta obtener un número congruente con 3 módulo 4. Luego se puede proceder sumando 20 = 5 × 4 en cada paso y calculando solo los restos de la división por 3. Esto da como resultado

4 mod 4 → 0. Continuar

4 + 5 = 9 mod 4 → 1. Continuar

9 + 5 = 14 mod 4 → 2. Continuar

14 + 5 = 19 mod 4 → 3. Bien, continuemos considerando los restos módulo 3 y sumando 5 × 4 = 20 cada vez.

19 módulo 3 → 1. Continuar

19 + 20 = 39 mod 3 → 0. Bien, este es el resultado.

Este método funciona bien para cálculos manuales con un producto de módulos no demasiado grande. Sin embargo, es mucho más lento que otros métodos para productos de módulos muy grandes. Si bien es considerablemente más rápido que la búsqueda sistemática, este método también tiene una complejidad temporal exponencial y, por lo tanto, no se utiliza en computadoras.

La prueba constructiva de existencia muestra que, en el caso de dos módulos , la solución puede obtenerse mediante el cálculo de los coeficientes de Bézout de los módulos, seguido de unas pocas multiplicaciones, sumas y reducciones módulo${\displaystyle n_{1}n_{2}}$(para obtener un resultado en el intervalo${\displaystyle (0,n_{1}n_{2}-1)}$). Dado que los coeficientes de Bézout pueden calcularse con el algoritmo euclidiano extendido , todo el cálculo tiene, como máximo, una complejidad temporal cuadrática de${\displaystyle O((s_{1}+s_{2})^{2}),}$dónde${\displaystyle s_{i}}$denota el número de dígitos de${\displaystyle n_{i}.}$

Para más de dos módulos, el método para dos módulos permite reemplazar cualquier par de congruencias por una sola congruencia módulo el producto de los módulos. Al iterar este proceso, se obtiene finalmente la solución con una complejidad cuadrática en el número de dígitos del producto de todos los módulos. Esta complejidad temporal cuadrática no depende del orden en que se reagrupan los módulos. Se pueden reagrupar los dos primeros módulos, luego reagrupar el módulo resultante con el siguiente, y así sucesivamente. Esta estrategia es la más fácil de implementar, pero también requiere más cálculos con números grandes.

Otra estrategia consiste en particionar los módulos en pares cuyos productos tengan tamaños comparables (en la medida de lo posible), aplicar en paralelo el método de dos módulos a cada par e iterar con un número de módulos aproximadamente dividido entre dos. Este método permite una fácil paralelización del algoritmo. Además, si se utilizan algoritmos rápidos (es decir, algoritmos que funcionan en tiempo cuasilineal ) para las operaciones básicas, este método proporciona un algoritmo para todo el cálculo que funciona en tiempo cuasilineal.

En el ejemplo actual (que tiene solo tres módulos), ambas estrategias son idénticas y funcionan de la siguiente manera.

La identidad de Bézout para 3 y 4 es

${\displaystyle 1\times 4+(-1)\times 3=1.}$

Sustituyendo esto en la fórmula dada para probar la existencia se obtiene

${\displaystyle 0\times 1\times 4+3\times (-1)\times 3=-9}$

Para una solución de las dos primeras congruencias, las otras soluciones se obtienen sumando a −9 cualquier múltiplo de 3 × 4 = 12. Se puede continuar con cualquiera de estas soluciones, pero la solución 3 = −9 + 12 es menor (en valor absoluto ) y, por lo tanto, probablemente conduce a un cálculo más sencillo.

La identidad de Bézout para 5 y 3 × 4 = 12 es

${\displaystyle 5\times 5+(-2)\times 12=1.}$

Aplicando la misma fórmula nuevamente, obtenemos una solución al problema:

${\displaystyle 5\times 5\times 3+12\times (-2)\times 4=-21.}$

Las otras soluciones se obtienen sumando cualquier múltiplo de 3 × 4 × 5 = 60 , y la solución positiva más pequeña es −21 + 60 = 39 .

El sistema de congruencias resuelto por el teorema chino del resto puede reescribirse como un sistema de ecuaciones diofánticas lineales :

${\displaystyle {\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}}$

donde los enteros desconocidos son${\displaystyle x}$y el${\displaystyle x_{i}.}$Por lo tanto, cualquier método general para resolver dichos sistemas puede utilizarse para hallar la solución del teorema chino del resto, como la reducción de la matriz del sistema a la forma normal de Smith o a la forma normal de Hermite . Sin embargo, como suele ocurrir al utilizar un algoritmo general para un problema más específico, este enfoque resulta menos eficiente que el método de la sección anterior, basado en el uso directo de la identidad de Bézout .

Un caso especial del teorema chino del resto para polinomios es la interpolación de Lagrange . Para ello, consideremos k polinomios mónicos de grado uno:

${\displaystyle P_{i}(X)=X-x_{i}.}$

Son coprimos por pares si el${\displaystyle x_{i}}$son todos diferentes. El resto de la división por${\displaystyle P_{i}(X)}$de un polinomio${\displaystyle P(X)}$es${\displaystyle P(x_{i})}$, por el teorema del resto polinomial .

Ahora, dejemos${\displaystyle A_{1},\ldots ,A_{k}}$sean constantes (polinomios de grado 0) en${\displaystyle K.}$Tanto la interpolación de Lagrange como el teorema chino del resto afirman la existencia de un polinomio único.${\displaystyle P(X),}$de grado menor que${\displaystyle k}$de tal manera que

${\displaystyle P(x_{i})=A_{i},}$

por cada${\displaystyle i.}$

La fórmula de interpolación de Lagrange es exactamente el resultado, en este caso, de la construcción anterior de la solución. Más precisamente, sea

${\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}}$

La descomposición en fracciones parciales de${\displaystyle {\frac {1}{Q(X)}}}$es

${\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}.}$

De hecho, al reducir el lado derecho a un denominador común se obtiene

${\displaystyle \sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}},}$

y el numerador es igual a uno, ya que es un polinomio de grado menor que${\displaystyle k,}$que toma el valor uno por${\displaystyle k}$diferentes valores de${\displaystyle X.}$

Utilizando la fórmula general anterior, obtenemos la fórmula de interpolación de Lagrange:

${\displaystyle P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.}$

La interpolación de Hermite es una aplicación del teorema chino del resto para polinomios univariados, que puede involucrar módulos de grados arbitrarios (la interpolación de Lagrange involucra solo módulos de grado uno).

El problema consiste en encontrar un polinomio del menor grado posible, de tal manera que el polinomio y sus primeras derivadas tomen valores dados en algunos puntos fijos.

Más precisamente, dejemos${\displaystyle x_{1},\ldots ,x_{k}}$ser${\displaystyle k}$elementos del terreno${\displaystyle K,}$y, para${\displaystyle i=1,\ldots ,k,}$dejar${\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}}$sean los valores del primero${\displaystyle r_{i}}$derivadas del polinomio buscado en${\displaystyle x_{i}}$(incluida la derivada de orden 0, que es el valor del polinomio mismo). El problema consiste en encontrar un polinomio${\displaystyle P(X)}$de tal manera que su j -ésima derivada toma el valor${\displaystyle a_{i,j}}$en${\displaystyle x_{i},}$para${\displaystyle i=1,\ldots ,k}$y${\displaystyle j=0,\ldots ,r_{j}.}$

Consideremos el polinomio

${\displaystyle P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}.}$

Este es el polinomio de Taylor de orden${\displaystyle r_{i}-1}$en${\displaystyle x_{i}}$, del polinomio desconocido${\displaystyle P(X).}$Por lo tanto, debemos tener

${\displaystyle P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}.}$

Por el contrario , cualquier polinomio${\displaystyle P(X)}$que satisface estas${\displaystyle k}$congruencias, en particular verifica, para cualquier${\displaystyle i=1,\ldots ,k}$

${\displaystyle P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}}$

por lo tanto${\displaystyle P_{i}(X)}$es su polinomio de Taylor de orden${\displaystyle r_{i}-1}$en${\displaystyle x_{i}}$, eso es,${\displaystyle P(X)}$resuelve el problema inicial de interpolación de Hermite. El teorema chino del resto afirma que existe exactamente un polinomio de grado menor que la suma de los${\displaystyle r_{i},}$que satisface estas${\displaystyle k}$congruencias.

Existen varias formas de calcular la solución.${\displaystyle P(X).}$Se puede utilizar el método descrito al principio de la sección «  Sobre anillos de polinomios univariados y dominios euclidianos ». También se pueden utilizar las construcciones dadas en las secciones «  Existencia (prueba constructiva)» o «  Existencia (prueba directa)» .

Dejar${\displaystyle I_{1},I_{2},\dots ,I_{k}}$sean ideales bilaterales coprimos por pares con${\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}$y

${\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}$

Sea el isomorfismo definido anteriormente.${\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)}$ser el elemento de${\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})}$cuyos componentes son todos 0 excepto el i- ésimo que es 1 , y${\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}$

El${\displaystyle e_{i}}$son idempotentes centrales que son ortogonales por pares ; esto significa, en particular, que${\displaystyle e_{i}^{2}=e_{i}}$y${\displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$para cada i y j . Además, uno tiene${\textstyle e_{1}+\cdots +e_{n}=1,}$y${\displaystyle I_{i}=R(1-e_{i}).}$

En resumen, este teorema generalizado del resto chino es la equivalencia entre dar ideales bilaterales coprimos por pares con intersección cero, y dar idempotentes centrales y ortogonales por pares que ^suman 1. ^[ 20 ^]

El teorema chino del resto se ha utilizado para construir una numeración de Gödel para secuencias , que está involucrada en la demostración de los teoremas de incompletitud de Gödel .

El algoritmo FFT de factor primo (también llamado algoritmo de Good-Thomas) utiliza el teorema chino del resto para reducir el cálculo de una transformada rápida de Fourier de tamaño${\displaystyle n_{1}n_{2}}$al cálculo de dos transformadas rápidas de Fourier de menor tamaño${\displaystyle n_{1}}$y${\displaystyle n_{2}}$(siempre que${\displaystyle n_{1}}$y${\displaystyle n_{2}}$son coprimos).

La mayoría de las implementaciones de RSA utilizan el teorema chino del resto durante la firma de certificados HTTPS y durante el descifrado.

El teorema chino del resto también se puede utilizar en el reparto de secretos , que consiste en distribuir un conjunto de partes entre un grupo de personas que, en conjunto (pero ninguna individualmente), pueden recuperar un secreto determinado a partir de dicho conjunto. Cada parte se representa mediante una congruencia, y la solución del sistema de congruencias utilizando el teorema chino del resto es el secreto que se va a recuperar. El reparto de secretos mediante el teorema chino del resto utiliza, junto con el propio teorema, secuencias especiales de números enteros que garantizan la imposibilidad de recuperar el secreto a partir de un conjunto de partes con una cardinalidad menor a un valor determinado .

Las técnicas de resolución de ambigüedad de alcance utilizadas con radares de frecuencia de repetición de pulsos media pueden considerarse un caso especial del teorema chino del resto.

Dada una sobreyección${\displaystyle \mathbb {Z} /n\to \mathbb {Z} /m}$de grupos abelianos finitos , podemos usar el teorema chino del resto para dar una descripción completa de cualquier aplicación de este tipo. En primer lugar, el teorema da isomorfismos

${\displaystyle {\begin{aligned}\mathbb {Z} /n&\cong \mathbb {Z} /p_{n_{1}}^{a_{1}}\times \cdots \times \mathbb {Z} /p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}}$

dónde${\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}}$. Además, para cualquier mapa inducido

${\displaystyle \mathbb {Z} /p_{n_{k}}^{a_{k}}\to \mathbb {Z} /p_{m_{l}}^{b_{l}}}$

de la sobreyección original, tenemos${\displaystyle a_{k}\geq b_{l}}$y${\displaystyle p_{n_{k}}=p_{m_{l}},}$ya que para un par de primos${\displaystyle p,q}$, las únicas sobreyecciones no nulas

${\displaystyle \mathbb {Z} /p^{a}\to \mathbb {Z} /q^{b}}$

se puede definir si${\displaystyle p=q}$y${\displaystyle a\geq b}$.

Estas observaciones son fundamentales para la construcción del anillo de enteros profinitos , que se define como el límite inverso de todas esas aplicaciones.

Teorema de Dedekind sobre la independencia lineal de caracteres. Sea M un monoide y k un dominio de integridad , visto como un monoide al considerar la multiplicación en k . Entonces, cualquier familia finita ( f _i ) _{i ∈ I}   de homomorfismos de monoides distintos f _i : M → k es linealmente independiente . En otras palabras, toda familia ( α _i ) _{i ∈ I} de elementos α _i ∈ k que satisface  

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}$

debe ser igual a la familia (0) _{i ∈ I} .

Demostración. Primero supongamos que k es un cuerpo ; de lo contrario, reemplacemos el dominio de integridad k por su cuerpo cociente , y nada cambiará. Podemos extender linealmente los homomorfismos de monoides f _i : M → k a homomorfismos de k - álgebras F _i : k [ M ] → k , donde k [ M ] es el anillo de monoides de M sobre k . Entonces, por linealidad, la condición   

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0,}$

rendimientos

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0.}$

A continuación, para i , j ∈ I ; i ≠ j las dos aplicaciones k-lineales F _i  : k [ M ] → k y F _j  : k [ M ] → k no son proporcionales entre sí. De lo contrario, f _i y f _j también serían proporcionales y, por lo tanto, iguales, ya que como homomorfismos de monoides satisfacen: f _i (1) = 1 = f _j (1) , lo cual contradice la suposición de que son distintas.      

Por lo tanto, los núcleos Ker F _i y Ker F _j son distintos. Dado que k [ M ]/Ker F _i ≅ F _i ( k [ M ]) = k es un cuerpo, Ker F _i es un ideal maximal de k [ M ] para todo i en I . Debido a que son distintos y maximales, los ideales Ker F _i y Ker F _j son coprimos siempre que i ≠ j . El Teorema Chino del Resto (para anillos generales) produce un isomorfismo:

${\displaystyle {\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

dónde

${\displaystyle K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.}$

En consecuencia, el mapa

${\displaystyle {\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

es sobreyectiva. Bajo los isomorfismos k [ M ]/Ker F _i → F _i ( k [ M ]) = k , la aplicación Φ corresponde a:

${\displaystyle {\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}}$

Ahora,

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}$

rendimientos

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

para cada vector ( u _i ) _{i ∈ I} en la imagen del mapa ψ . Dado que ψ es sobreyectiva, esto significa que

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

para cada vector

${\displaystyle \left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.}$

En consecuencia, ( α _i ) _{i ∈ I} = (0) _{i ∈ I} . QED.