中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性

簡介

中國餘式定理Chinese Remainder Theorem(CRT)在密碼理論當中屬於重要的概念，尤其在RSA密碼系統裡也扮演重要的角色。

中國餘式定理

CRT主要想解決的問題是找到共同的數針對不同的模運算式，這種在像是RSA密碼系統計算合成數 $quicklatex.com-8cef6b4f4f69246484c07bb5de49b6a5_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 取決於 $quicklatex.com-1b59fd25aed1ecf6146b4460c9dc464d_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 及 $quicklatex.com-c8634923e8db15ae8bdbfe9af002bfef_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 兩個質數很有幫助。

對於 $quicklatex.com-e26e94cc93726bc95b7541e644e2b40c_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 以及 $quicklatex.com-d2b4e342f448aef0dfb807b3ce9f9306_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ， $quicklatex.com-769f9a8a51f8dd389568a8ab4560fbdd_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ，能夠組成各自的聯立方程式:

$quicklatex.com-125e9952e2f6d63e93fdc91f33ab04d6_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

透過上述的每一個聯立方程式可以找出 $quicklatex.com-4eded1e1dff989904cefab30257782dc_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ :

$quicklatex.com-86a50b750ea162b73a6eb51a3ff573a4_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

其中 $quicklatex.com-0af8e9573012417f815a4096ff1b257e_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 以及 $quicklatex.com-d705d7d3fac33a18596deca9cecb5cd6_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

舉例:

$quicklatex.com-594ed81bc332515fb39f9b8a8c19a53c_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 可以組成下列的聯立方程式:

$quicklatex.com-4d69dc5983a6bb0eed4bad172e4bd41d_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

並且 $quicklatex.com-f068eec944c4db7c035cf9685612aee6_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

接著找各個 $quicklatex.com-bcdf9b26d7ef33214952964a86c23054_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 的反元素，

$quicklatex.com-b603f3c0a8d2669c5603767cfc7d8ec9_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

這樣就能可以找到 $quicklatex.com-4eded1e1dff989904cefab30257782dc_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ :

$quicklatex.com-d73c2bdf1d78f5f64fecb7baee19b2d5_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

同構 Isomorphism

符合CRT的聯立方程式具有同構的特性，假設 $quicklatex.com-8eab39916516f3719f3fc5154627c4d2_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 以及 $quicklatex.com-d1f3351443b46d1ac205ac87e4247417_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ， $quicklatex.com-769f9a8a51f8dd389568a8ab4560fbdd_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

$quicklatex.com-2f013357ed6a90b2da59d7de6b9b3e8c_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

使用CRT找到 $quicklatex.com-4eded1e1dff989904cefab30257782dc_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 透過 $quicklatex.com-6ff583b0390b7a69aaa1c36ae2edcc72_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

舉例：

$quicklatex.com-87c2e0da70f64767061cd3939486f4ed_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ，可以看成 $quicklatex.com-193c2ace3b902f999d56d660808bb4b6_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

可以看成 $quicklatex.com-8a5086b1b2e35a1629a07e7d66ad1e08_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 等等

$quicklatex.com-9c9b562b34a48392472eefdcfaab995d_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 可以看成 $quicklatex.com-a7081f4e5e62fa8ad1376b0b895c20f6_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

或者 $quicklatex.com-ffebfef960f926c29a724c1886c6cac3_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 可以看成 $quicklatex.com-fd46719def64d45564ebe8bb96da95c1_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

前面提到主要對RSA有用就是因為有同構的特性:

計算 $quicklatex.com-7493bc0ea738e24a55e9478842a88b84_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ， $quicklatex.com-4f8b2d2138d142a5811e67da07b5f8ab_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 可以想成 $quicklatex.com-8cef6b4f4f69246484c07bb5de49b6a5_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ，代表 $quicklatex.com-8cef6b4f4f69246484c07bb5de49b6a5_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 的群來自 $quicklatex.com-fc64f1cb525c6964756b599786e9e07d_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ，以及 $quicklatex.com-ed09fd11baef9cb2e3d29d2b2cfa9fc0_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 的長度。

$quicklatex.com-23d2c9616008e7bca5deca5e73e0d706_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$

所以 $quicklatex.com-ac444637f670f34bc65f509458655d4c_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ ，計算 $quicklatex.com-eb9462be1af5171b9038d7baf084ad09_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 需要 $quicklatex.com-5290f713c5a9d2d12649f922822a7da3_l3 中國餘式定理 Chinese Remainder Theorem 與同構 Isomorphism 特性$ 的時間。