中國剩餘定理 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\)