Diferencia entre revisiones de «Teorema chino del resto»
m r2.5.5) (robot Eliminado: ur:چینی تقسیم باقی مسلئہ اثباتی |
Sin resumen de edición |
||
Línea 1: | Línea 1: | ||
El '''teorema |
El '''teorema ming del resto''' es un resultado sobre [[congruencia]]s en [[teoría de números]] y sus generalizaciones en [[álgebra abstracta]].E cual fue creado por el nenuco culturista, Joaquin Sanchez Ming samurai delk a dinastia sin Minga El enunciado dice: |
||
si la tienes una minga pequeña mejor que sea juguetona y petate con un candao chino. |
|||
{{teorema |
{{teorema |
Revisión del 09:33 8 abr 2011
El teorema ming del resto es un resultado sobre congruencias en teoría de números y sus generalizaciones en álgebra abstracta.E cual fue creado por el nenuco culturista, Joaquin Sanchez Ming samurai delk a dinastia sin Minga El enunciado dice:
si la tienes una minga pequeña mejor que sea juguetona y petate con un candao chino.
|
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
Más aún, todas las soluciones x de este sistema son congruentes módulo el producto .
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:
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 , donde es un producto de dos primos y . Tamaños habituales para 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 y es la longitud de bit de , haciendo y considerablemente menor que . 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. p. 238. ISBN 978-0-387-94293-3.