Teorema chino del resto

De Wikipedia, la enciclopedia libre

Sean tales que (primos relativos).

Entonces dados cualesquiera , tal que:

y

Y además si existen otros que satisfagan las dos congruencias anteriores entonces:

[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 n₁, n₂, …, n_k son enteros coprimos dos a dos. Entonces, para enteros dados a₁,a₂, …, a_k, existe un entero x que resuelve el sistema de congruencias simultáneas

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto N = n₁n₂...n_k.

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

Todas las soluciones x son entonces congruentes módulo el mínimo común múltiplo de los n_i.

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 una gran cantidad de tiempo. Usando el teorema chino del resto los cálculos pueden ser transportados del anillo al anillo . 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".