中國餘數定理 (Chinese Remainder Theorem,簡稱 CRT) 經常是工程學裡面常用的一種轉換域,很多人不知道當初在大學離散數學中學這個做什麼,但是在不少計算的設計都會運用到 CRT。由於電腦 CPU 架構中的運算單位是 32-bits 或者 64-bits (也許在未來會更長),但值域高達 128-bits 或者 512-bits 以上模擬運算成了麻煩之處。
回顧中國餘數定理 CRT
$$ (S): \left\{\begin{matrix}
x \equiv a_1 \mod m_1 \\
x \equiv a_2 \mod m_2 \\
\vdots \\
x \equiv a_n \mod m_n
\end{matrix}\right. $$
構造法解 CRT
很多人會納悶通解為什麼長那樣,原因很簡單,要滿足方程組每一條式子,勢必對於 $a_i t_i M_i$ 要滿足 $x \equiv a_i \mod m_i$ ,因此 $a_i t_i M_i \equiv a_i (t_i M_i) \mod m_i \equiv a_i \mod m_i$ 成立,但是 $ \forall i \neq j$,滿足 $a_i t_i M_i \equiv a_i (t_i M_i) \mod m_j \equiv 0 \mod m_j$
來個簡單運用,來計算簡單的 RSA 加解密,特化其中的數學運算。
$$M \equiv C^d \mod n$$
$n = p \times q$,其中 $p, q$ 是兩個不同的質數,已知 $C, d, p, q$,請求出 $M$。
88 7 17 11 11 23 17 11
11 88
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
37303 | s014052@stu. ... (112程式設計金手三) | b431 | 162 | 2023-08-31 09:07 |