【摘要】
今天這集一口氣講了不少東西，從韓信點兵到同餘符號的介紹，再到中國餘式定理，然後再到 RSA 密碼系統的介紹，最後再以中國餘式定理在 RSA 上的應用。這集一開始很輕鬆，但後面很陡，這也是我做這個系列的主要精神之一，短時間內把基本到進階甚至值得研究的課題串起來。
【本系列其他影片】
上集 👉 從高中機率抽球問題，講到大學機率論的二項分布與卜松分布，最後教你如何開除員工 (https://youtu.be/gN8TWD1hvfw)
下集 👉 從高中數學排列組合的加法原理和乘法原理，講到大學離散數學的圖論的五色定理證明 (https://youtu.be/bhB5hubDgss)
【版權宣告】
本影片版權為張旭 (張舜為) 老師所有
嚴禁用於任何商業用途⛔
如果有學校老師在課堂使用我的影片的話
請透過以下聯絡方式通知我讓我知道，謝謝
FB：https://www.facebook.com/changhsumath
IG：https://www.instagram.com/changhsumath
中國剩餘定理 在 Re: [代數]CRT 中國餘數定理- 看板Math - 批踢踢實業坊 的美食出口停車場
※ 引述《ericpoto (Eric)》之銘言：
: 初學CRT遇到了理解方面得障礙
: 我只理解取819是因為7.9.13互質
: 而7x9x13=819，則在mod819下有解
: 接下來就完全不理解了
: 題目如下：
: X≡5 (mod7)
: X≡4 (mod9)
: X≡3 (mod13)
: 解如下：
: r1=5,r2=4,r3=3
: n1=7,n2=9,n3=13
: n=n1n2n3=819
: N1=n/n1=117
: N2=n/n2=91
: N3=n/n3=63
: M1=N1¯(mod n1)=3
: M2=N2¯(mod n2)=1
: M3=N3¯(mod n3)=6
: 取X≡r1M1N1+r2M2N2+r3M3N3 (mod 819)
: 我的問題是
: 1.為何要取N1=n/n1,是為了甚麼準備?
: 2.M1不是在(mod n1)下的N1的inverse嗎?(類推M2.M3)
: 為何可以代入(mod n1n2n3)的式子中?
: 3.為何X≡r1M1N1+r2M2N2+r3M3N3 (mod 819)
這三個問題要一起回答
中國剩餘定理最早的出處是韓信點兵相信這你也知道
韓信點兵的原題以現代數學語言來寫就是:
已知 X≡r1 (mod 3) 求解 X
X≡r2 (mod 5)
X≡r3 (mod 7)
那一首歌謠解法若也寫成現代數學型式就是
X ≡ 70*r1 + 21*r2 + 15*r3 (mod 105)
這式子裡的 70 21 15 的地位就是上述公式解當中的 M1*N1 M2*N2 M3*N3
它所代表的意義是這樣的:
70≡1 (mod 3) 21≡0 (mod 3) 15≡0 (mod 3)
70≡0 (mod 5) 21≡1 (mod 5) 15≡0 (mod 5)
70≡0 (mod 7) 21≡0 (mod 7) 15≡1 (mod 7)
由此很容易驗證 X = 70*r1+21*r2+15*r3 確實滿足原來的三條同餘式
M1 跟 N1 等等的計算過程便是要找出對任意模數具有如上性質的乘數來
以第一直欄為例 n1 = 3, n2 = 5, n3 = 7
所以 N1 = n/n1 = n2*n3 = 35 可以被 n2 和 n3 整除 滿足了第一直欄下兩條
再來要找一個 N1 的倍數使得這個倍數除以 3 餘 1
所以就直接求 M1 = 35¯(mod 3) = 2 這即表示 2*N1 除以 3 會餘 1
所以 2*35 = 70 就是我們要找的第一個乘數 其餘的依此類推
這便是這一套公式的由來
(順帶一提, 這套演算法在古中國叫做「大衍求一術」
總結這套算法的是宋朝的數學家秦九韶
名字裡的「一」就是指上面的那些同餘表格中的那些餘一
大衍求一術就是在計算 M1*N1 等等的這些乘數的演算法)
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ ＨＡＲＵＨＩ █████ ＜■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ＩＳＭ By-gamejye ￠|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.19.119
... <看更多>