中國剩餘定理 Chinese remainder theorem

RSA演算法的解碼方法是$C^d \mod N$，$d$ 是一個很大的數，要算這個值比較辛苦，可以利用中國剩餘定理來簡化。
中國剩餘定理處理的問題就是韓信點兵這種題目

兵不知其數，三三數之剩二，五五數之剩三，七七數之剩二

寫成數學式就是
$\left\{ \begin{matrix} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\x \equiv 2 \pmod{7} \end{matrix} \right.$

以下紀錄幾種計算方式

方法1.利用同餘的加性

將題目拆成成3部分

$\left\{ \begin{matrix} a \equiv 2 \pmod{3} \\ a \equiv 0 \pmod{5} \\a \equiv 0 \pmod{7} \end{matrix} \right.$    $\left\{ \begin{matrix} b \equiv 0 \pmod{3} \\ b \equiv 3 \pmod{5} \\b \equiv 0 \pmod{7} \end{matrix} \right.$    $\left\{ \begin{matrix} c \equiv 0 \pmod{3} \\ c \equiv 0 \pmod{5} \\c \equiv 2 \pmod{7} \end{matrix} \right.$

$\Rightarrow \left\{ \begin{matrix} (a+b+c) \equiv 2 \pmod{3} \\ (a+b+c) \equiv 3 \pmod{5} \\(a+b+c) \equiv 2 \pmod{7} \end{matrix} \right.$

分別求出 $a,b,c$ ，就能得到一組解

$\left\{ \begin{matrix} a \equiv 2 \pmod{3} \\ a \equiv 0 \pmod{5} \\a \equiv 0 \pmod{7} \end{matrix} \right.$
$\Rightarrow a=35k$，$k=1$ 為其中一組解，則$a=35$

同樣的方式，可以算出$b=63,c=30$
$a+b+c=35+63+30=128$，$128$ 就是 $x$ 的其中一組解
$\Rightarrow x \equiv 128 \pmod {105}$
$\Rightarrow x \equiv 23 \pmod {105}$


方法2.利用同餘的加性和乘性

與方法1類似，將題目拆成成3部分

$\left\{ \begin{matrix} a \equiv 1 \pmod{3} \\ a \equiv 0 \pmod{5} \\a \equiv 0 \pmod{7} \end{matrix} \right.$    $\left\{ \begin{matrix} b \equiv 0 \pmod{3} \\ b \equiv 1 \pmod{5} \\b \equiv 0 \pmod{7} \end{matrix} \right.$    $\left\{ \begin{matrix} c \equiv 0 \pmod{3} \\ c \equiv 0 \pmod{5} \\c \equiv 1 \pmod{7} \end{matrix} \right.$

求出 $a,b,c$ 後，$2a+3b+2c$ 就是一組解

$\left\{ \begin{matrix} a \equiv 1 \pmod{3} \\ a \equiv 0 \pmod{5} \\a \equiv 0 \pmod{7} \end{matrix} \right.$
$\Rightarrow a=35k$，$k=2$ 為其中一組解，則$a=70$
因為 mod 的數很小，很容易可以挑出來，但是希望可以用一種比較有系統的方式去求出$a$
$35k \equiv 1 \pmod 3$
其實就是在算$35$對模$3$的模反原素，可以利用輾轉相除法的過程求得，這樣以後遇到比較大的模數也能有效率的算出$k$

利用相同的方法，$b=21,c=15$
$\Rightarrow 2a+3b+2c=140+63+30=233$
$\Rightarrow x \equiv 128 \pmod {105}$
$\Rightarrow x \equiv 23 \pmod {105}$

孫子算經裡就是用這種解法

今有物，不知其數。三、三數之，賸二；五、五數之，賸三；七、七數之，賸二。問物幾何？
答曰：二十三。
術曰：「三、三數之，賸二」，置一百四十；「五、五數之，賸三」，置六十三；「七、七數之，賸二」，置三十。并之，得二百三十三。以二百一十減之，即得。凡三、三數之，賸一，則置七十；五，五數之，賸一，則置二十一；七、七數之，賸一，則置十五。一百六以上，以一百五減之，即得。

算法統宗(明 程大位)

物不知總 孫子歌曰 又云韓信點兵也

三人同行七十稀 五樹梅花廿一枝
七子團員正半月 除百令五便得知

今有物不知數只云三數剩二箇五數剩三箇七數剩二箇問共若干
答曰 共二十三箇

射鵰英雄傳裡黃蓉念給瑛姑的就是這首歌訣，桃花島的人真是厲害，明代的書隨口就念了出來

這種方法很有系統，先求反原素，乘上餘數，再相加，很適合拿來寫程式

方法3.利用代數解題

$\left\{ \begin{matrix} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\x \equiv 2 \pmod{7} \end{matrix} \right.$
$\Rightarrow\left\{ \begin{matrix} x=3a+2 \\ x=5b+3 \\x =7c+2 \end{matrix} \right.$

$3a+2 \equiv 3 \pmod 5$
$3a \equiv 1 \pmod 5$
$a \equiv 2 \pmod 5$
$\Rightarrow a=5b'+2$
$\Rightarrow x=3a+2=3(5b'+2)+2=15b'+8$

$15b'+8 \equiv 2 \pmod 7$
$15b' \equiv 1 \pmod 7$
$b' \equiv 1 \pmod 7$
$\Rightarrow b'=7c'+1$

$\Rightarrow x=15b'+8=15(7c'+1)+8=105c'+23$