Part II: Structures
第九章：數論
數論研究整數的性質，它是密碼學的基石。本章將介紹整除、模運算以及著名的 RSA 加密演算法。
9.1 & 9.2 整除性與最大公因數
若 $n$ 除以 $d$ 的餘數為 0，則稱 $d$ 整除 $n$，記作 $d | n$。
最大公因數 $gcd(a, b)$ 是能同時整除 $a$ 和 $b$ 的最大整數。
最大公因數 $gcd(a, b)$ 是能同時整除 $a$ 和 $b$ 的最大整數。
🧪 歐幾里得算法互動
歐幾里得算法 是計算 GCD 的高效方法。請輸入兩個數字：
等待輸入...
9.6 模運算
模運算關注的是除法後的「餘數」。我們稱 $a \equiv b \pmod n$ 如果 $n$ 整除 $(a-b)$。這就像一個時鐘，轉了一圈後數字重複。
9.11 RSA 公開金鑰加密
RSA 是一種非對稱加密演算法：公鑰用於加密，私鑰用於解密。其安全性基於大整數分解的困難性。
🔒 簡化 RSA 演示 (使用小質數)
步驟 1: 選擇質數
步驟 2: 計算參數
n = p * q = 3233
φ(n) = (p-1)(q-1) = 3120
選擇 e (與 φ 互質): 17
計算 d (e 的模反元素): 2753
φ(n) = (p-1)(q-1) = 3120
選擇 e (與 φ 互質): 17
計算 d (e 的模反元素): 2753
加密: c = m^e mod n
解密: m = c^d mod n
解密: m = c^d mod n
註：此處使用小質數演示。實際應用中，質數長度可達數千位。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)