Diferencia entre revisiones de «Teorema chino del resto»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 16:01 21 abr 2010

El teorema chino del resto es un resultado sobre congruencias en teoría de números y sus generalizaciones en álgebra abstracta. El enunciado dice:

Sean $n,m\in \mathbb {N}$ tales que $\operatorname {mcd} (n,m)=1\,$ (primos relativos).
Entonces dados cualesquiera $b_{1},b_{2}\in \mathbb {Z}$ , $\exists x\in \mathbb {Z}$ tal que:

$x\equiv b_{1}{\pmod {n}}$ y

$x\equiv b_{2}{\pmod {m}}$

Y además, si existen otros $v,w\in \mathbb {Z}$ que satisfagan las dos congruencias anteriores entonces:

$v\equiv w{\pmod {n\cdot m}}$

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

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto $N=n_{1}n_{2}...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:

a_{i}\equiv a_{j}{\pmod {\operatorname {mcd} (n_{i},n_{j})}}\qquad {\mbox{para todo }}i{\mbox{ y }}j.\,\!

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).

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 $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 ${\mathbb {Z}}_{n}$ al anillo ${\mathbb {Z}}_{p}\times {\mathbb {Z}}_{q}$ . 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".

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.

@@ Línea 1: / Línea 1: @@
+El '''teorema chino del resto''' es un resultado sobre [[congruencia]]s en [[teoría de números]] y sus generalizaciones en [[álgebra abstracta]]. El enunciado dice:
-'''中國剩餘定理'''（'''Chinese Remainder Theorem'''，'''中国余数定理'''），古有「'''韓信點兵'''」、「'''孫子定理'''」、「'''鬼谷算'''」、「'''隔墻算'''」、「'''剪管術'''」、「'''秦王暗點兵'''」、「'''物不知數'''」之名，是[[數論]]中的一個重要命題。
+{{teorema
-== 物不知数 ==
+|1=Sean <math>n,m \in \mathbb{N}</math> tales que <math> \operatorname{mcd}(n, m) = 1 \,</math> ([[primos relativos]]).
-在中國古代著名數學著作《[[孫子算經]]》中，有一道題目叫做“物不知數”，原文如下：
-{{quote|有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？}}
-即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。
+Entonces dados cualesquiera <math>b_1,b_2 \in \mathbb{Z}</math>, <math>\exists x \in \mathbb{Z}</math> tal que:
-[[中国]][[数学家]][[秦九韶]]于[[1247年]]做出了完整的解答，口訣如下
-{{quote|三人同行七十希，五樹梅花廿一支，七子團圓正半月，除百零五便得知}}
-這個解法實際上是，首先利用秦九韶發明的[[大衍求一術]]求出5和7的最小公倍數35的倍數中除以3餘數為1的最小一個70（這個稱爲35相對于3的數論倒數），3和7的最小公倍數21相對于5的數論倒數21，3和5的最小公倍數15相對于7的數論倒數15。然後
-:<math>70 \times 2 + 21 \times 3 + 15 \times 2 = 233</math>
-便是可能的解之一。它加減3、5、7的最小公倍數105的若干倍仍然是解，因此最小的解為233除以105的餘數23。
+:<math>x \equiv b_1 \pmod n</math> y
-附注：这个解法并非最简，因为实际上35就符合除3余2的特性，所以最小解是：<math> 35 \times 1 + 21 \times 3 + 15 \times 2- 3 \times 5  \times 7 = 128 - 105 = 23</math> 最小解加上105的正整数倍都是解。
+:<math>x \equiv b_2 \pmod m</math>
+Y además, si existen otros <math>v,w \in \mathbb{Z}</math> que satisfagan las dos [[congruencia]]s anteriores entonces:
-== 形式描述 ==
-以上解法若推廣到一般情況，便得到了中國剩餘定理的一個構造性證明。
+:<math>v \equiv w \pmod {n \cdot m} </math>
-一般地，'''中國剩餘定理'''是指若有一些[[互质|两两互质]]的[[整数]] <math>m_1, m_2, \ldots, m_n</math>，则对任意的整数：<math>a_1, a_2,...a_n</math>，以下联立[[同餘]]方程组对模 <math>m_1 m_2 \cdots m_n</math> 有公解：
+|2=
+}}
+== Enunciado del teorema ==
-:<math>\left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end{matrix} \right.</math>
+La forma original del teorema, contenida en un libro del [[siglo III]] por
-== 克罗内克符号 ==
+el matemático chino [[Sun Tzu (matemático)|Sun Tzu]]
-为了便于表述，对任意的[[正整数]]<math>\mathbf{i,j}</math>用一个常用[[函数]]<math>\zeta_{i,j}</math>表示，称之为[[克罗内克]]符号(Kronecker).定义：
+[http://www.economist.com/science/displaystory.cfm?story_id=8881479] y
-:<math>\zeta_{i,j} =\begin{cases} 1, \; i=j \\ 0, \; i \ne j \end{cases}</math>
+posteriormente publicado en [[1247]] por [[Qin Jiushao]], es un enunciado sobre
-使用该符号，即可给出上述一般同餘方程组的求解过程，分两步完成
+congruencias simultáneas (ver [[aritmética modular]]).
-* 对每个<math>1 \le i \le k</math>，先求出[[正整数]]<math>b_i</math>满足<math>b_i \equiv \zeta_{i,j} \pmod {m_j}</math>，即所求的<math>b_i</math>满足条件：<math>b_i \;\bmod\; m_i = 1</math>，但被每个<math>m_j(i\ne j)</math>整除。其求法如下：记<math>r_i =m_{1} \cdots m_{i-1} m_{i+1} \cdots m_k</math>，根据条件<math>m_1 ,\cdots,m_k</math>两两互素，可知<math>r_i</math>和<math>m_i</math>也互素，故存在整数<math>c_i</math>和<math>d_i</math>使得<math>r_i c_i + m_i d_i=1</math>.令<math>b_i = r_i c_i</math>，则对每个<math>i \ne j</math>，相对应的<math>m_j</math>显然[[整除]]<math>b_i</math>，并且<math>b_i \equiv 1 \pmod {m_i}</math>。由此表明<math>b_i</math>即为所求。
-* 对于前述所求的<math>b_i</math>，令<math>x_0 = \sum_{i=1}^k a_ib_i</math>，则<math>x_0 \equiv a_i b_i \equiv a_i \pmod {m_i}</math>，这说明<math>x_0</math>为上述同餘方程组的一个解，从而所有的解可表示为<math>x = x_0 + n \prod_{i=1}^k m_i</math>，其中的n可以取遍所有的整数。
+Supongamos que ''n''<sub>1</sub>, ''n''<sub>2</sub>, …, ''n''<sub>''k''</sub>
-== 近世交换环及推广 ==
+son [[entero]]s [[coprimos dos a dos]]. Entonces, para enteros dados
-设<math>\mathbf{R}</math>为有[[单位元]]的[[交换环]]，<math>I_1,\cdots,I_n</math>为环<math>\mathbf{R}</math>的[[理想]]，并且当<math>i \ne j</math>时，<math>I_i + I_j = \mathbf{R}</math>，则有[[典范]]的环[[同构]]<math>\mathbf{R} /( I_1 \cap \cdots \cap I_n \cong  \mathbf{R} / I_1 \times \cdots \times \mathbf{R} I_n</math>，其中环同构由[[映射]]<math>\alpha +  I_1 \cap \cdots \cap  I_n \rightarrow (\alpha + I_1 , \alpha + I_2 ,\cdots, \alpha + I_n</math>）给出。
+''a''<sub>1</sub>,''a''<sub>2</sub>, …, ''a''<sub>''k''</sub>, existe un
+entero ''x'' que resuelve el sistema de congruencias simultáneas
+:<math>\begin{align}
-== 参考书目 ==
+ x &\equiv a_1 \pmod{n_1} \\
-''数学的100个基本问题''，靳平 主编，ISBN 7-5377-2171-8
+ x &\equiv a_2 \pmod{n_2} \\
+   &\vdots \\
+ x &\equiv a_k \pmod{n_k}
+\end{align}</math>
+Más aún, todas las soluciones ''x'' de este sistema son congruentes módulo el
-[[Category:同余]]
+producto <math>N = n_1 n_2 ... n_k</math>.
-[[Category:数学定理|Z]]
+Algunas veces, las congruencias simultáneas pueden ser resueltas aun si los
+''n<sub>i</sub>'''s no son coprimos a pares. Una solución ''x'' existe si y sólo
+si:
+:<math>a_i \equiv a_j \pmod{\operatorname{mcd}(n_i,n_j)} \qquad \mbox{para todo }i\mbox{ y }j
+. \,\! </math>
+Todas las soluciones ''x'' son entonces congruentes módulo el [[mínimo común múltiplo]]
+de los ''n<sub>i</sub>''.
+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 [[RSA|algoritmo RSA]], por ejemplo, los cálculos se hacen módulo <math>n</math>, donde
+<math>n</math> es un producto de dos primos <math>p</math> y <math>q</math>.
+Tamaños habituales para <math>n</math> son 1024, 2048 ó 4096 [[bit]]s, 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 <math>\Bbb{Z}_n</math> al anillo
+<math>\Bbb{Z}_p \times \Bbb{Z}_q</math>. La suma de las longitudes de bit de
+<math>p</math> y <math>q</math> es la longitud de bit de <math>n</math>,
+haciendo <math>p</math> y <math>q</math> considerablemente menor que <math>n</math>.
+Esto acelera mucho los cálculos. Nótese que las implementaciones del [[RSA|algoritmo RSA]]
+usando el teorema chino del resto son más susceptibles a ataques de "fault injection".
+== Referencias ==
+* {{cita libro
+| apellidos = Koblitz
+| nombre = Neal
+| enlaceautor = Neal Koblitz
+| editorial = Springer
+| título = A Course in Number Theory and Cryptography
+| edición = 2ª
+| año = 1998
+| ubicación = EE. UU.
+| isbn = 978-0-387-94293-3
+| páginas = 238
+}}
+[[Categoría:Teoremas de teoría de números|Chino del resto]]
 [[ar:مبرهنة الباقي الصيني]]
@@ Línea 42: / Línea 87: @@
 [[de:Chinesischer Restsatz]]
 [[en:Chinese remainder theorem]]
-[[es:Teorema chino del resto]]
 [[fa:قضیه باقیمانده چینی]]
 [[fi:Kiinalainen jäännöslause]]
@@ Línea 64: / Línea 108: @@
 [[ur:چینی تقسیم باقی مسلئہ اثباتی]]
 [[vi:Định lý số dư Trung Quốc]]
+[[zh:中国剩余定理]]
 [[zh-classical:韓信點兵]]