第九章：數論 — 動畫敘事
第一集 · Ch.9 數論
因數
你每次打開 LINE、逛 YouTube、用網路銀行，
手機都在做一件事——用一道數學謎題保護你的資料。
這道謎題的核心，只是你國中學過的東西：因數。
手機都在做一件事——用一道數學謎題保護你的資料。
這道謎題的核心，只是你國中學過的東西：因數。
輾轉相除法
gcd(48, 18) 怎麼算？每步取餘數，餘數為 0 時前一個除數就是答案。
| 48 = 18 × 2 + 12 | → gcd(18, 12) |
| 18 = 12 × 1 + 6 | → gcd(12, 6) |
| 12 = 6 × 2 + 0 | gcd = 6 ✓ |
自己試試看
輸入兩個數字後按計算…
模運算
14 mod 12 = 2 像時鐘一樣，超過就繞回去
14 mod 12 = 2
換個數試試
14 mod 12 = 2
RSA 公鑰加密
訊息
m = 123
m = 123
→
公鑰加密
me mod n
me mod n
→
密文
c = 855
c = 855
↑ 只有私鑰可以解密 cd mod n → 還原成 123
p = 61, q = 53
n = p × q = 3233
e = 17（公鑰）, d = 2753（私鑰）
加密：123¹⁷ mod 3233 = 855
解密：855²⁷⁵³ mod 3233 = 123 ✓
安全性來自：把 n 分解回兩個質數幾乎不可能——
n 夠大時，全宇宙的電腦算到宇宙滅亡都算不完。
n 夠大時，全宇宙的電腦算到宇宙滅亡都算不完。
小結
1 / 5
本頁為動畫敘事版。看完後可前往
完整第九章
進行互動練習（GCD 計算、模運算時鐘、RSA 加解密等）。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)