用中國剩餘定理進行模冪運算
我正在用中國剩餘定理學習模冪運算。
我從下面找到了一個很好的答案 如何使用歐拉函式和中國剩餘定理進行模冪運算？
但我無法理解施工的最後一步 $ C_p $ 和 $ C_q $ 很好。有人可以向我解釋嗎？此外，如果我讓 $ N = 55 = 11 \times 5 $ 代替 $ 5 \times 11 $ ，最後一步未能給出正確答案。
最後一步：
$$ M^e \bmod{pq}= C_q+q((C_p−C_q) \bmod p) $$
首先，你把最後一行弄錯了，它是
$$ M^e \bmod{pq} = C_q+q(q^{−1}(C_p−C_q) \bmod p) $$ CRT 的基本思想是，如果 $ a $ 和 $ b $ 是相對素數，工作模 $ ab $ 與工作模數相同 $ a $ 和模 $ b $ 分別地。在模冪運算的情況下，對一個元素模取冪 $ a $ 然後取模 $ b $ 比模數便宜得多 $ ab $ ，因為您可以使用較小的指數。
關於最後一步，它是標準的 CRT 計算，你有
$$ \left{\begin{array}{l} M^e \equiv C_p \pmod p \ M^e \equiv C_q \pmod q \end{array}\right. $$ 第二行給出 $ M^e = C_q+kq $ . 將其插入第一個給出 $ C_q+kq \equiv C_p \pmod p $ ， 所以 $ kq \equiv C_p-C_q \pmod p $ . 自從 $ p $ 和 $ q $ 是我們可以採取的相對主要的 $ q^{-1} \bmod p $ ， 所以 $ k \equiv q^{-1}(C_p-C_q) \pmod{p} $ ， 所以 $ k = q^{-1}(C_p-C_q) + k’p $ . 將其插入 $ M^e = C_q+kq $ 給出所需的表達式。