整數性質與密碼學基礎
數論是研究整數性質的數學分支，被稱為「數學的皇后」。在電腦科學中，數論扮演著核心角色，特別是在密碼學、編碼理論、演算法設計和資訊安全等領域。現代公鑰密碼系統（如 RSA、橢圓曲線密碼學）完全建立在數論的基礎之上。
整除性：對於整數 a 和 b（b≠0），若存在整數 q 使得 a = bq，則稱 b 整除 a，記作 b | a。
除法算法：對於任意整數 a 和正整數 b，存在唯一的商 q 和餘數 r 使得 a = bq + r，0 ≤ r < b。
最大公因數 (GCD)：歐幾里得演算法基於 gcd(a,b) = gcd(b, a mod b)，時間複雜度 O(log min(a,b))。擴展歐幾里得演算法可計算模反元素，是 RSA 加密的數學基礎。
同餘關係：a ≡ b (mod m) 若 m | (a-b)。同餘關係滿足自反性、對稱性、傳遞性、加法律和乘法律。
質數是大於 1 且只能被 1 和自身整除的自然數。算術基本定理：每個大於 1 的自然數都可以唯一分解為質數的乘積。
質數定理：π(x) ~ x / ln x，其中 π(x) 是小於 x 的質數數量。第 n 個質數約為 n ln n。
質數檢驗：埃拉託斯特尼篩法（找出範圍內的所有質數）、米勒-拉賓質數檢驗（機率性演算法）、AKS 質數檢驗（確定性多項式時間）。
RSA 公鑰密碼系統的安全性依賴於大質數分解的困難性。金鑰生成過程：隨機選擇兩個大質數 p, q，計算 n = p×q 和 φ(n) = (p-1)(q-1)，選擇 e 滿足 gcd(e, φ(n)) = 1，計算 d 使得 ed ≡ 1 mod φ(n)。
歐拉定理：若 gcd(m, n) = 1，則 m^{φ(n)} ≡ 1 (mod n)。這是 RSA 解密正確性的數學保證。