質數、同餘與密碼學：藏在那把鎖裡的數論

你每天按下的那把「鎖」，藏著一道質數謎題

當你在咖啡廳連上網路、登入銀行 App、或在網址列看到那個小小的鎖頭圖示時，背後其實正進行一場跨越兩千年的數學接力。希臘人歐幾里得（Euclid）在公元前三百年證明了「質數有無窮多個」，高斯（Gauss）在十九世紀把同餘（congruence）寫成一套優雅的符號系統，而今天，這些看似純粹、與生活毫無關係的結果，竟成了保護你信用卡號碼的最後一道防線。

數論（number theory）研究的是整數的性質。它曾被英國數學家哈第（G. H. Hardy）驕傲地稱為「最無用」的學問——而歷史開了他一個玩笑：正是這份「無用」，撐起了整個現代資訊安全。讓我們從最基本的磚塊——質數——開始，一路走到密碼學的門口。

質數：整數世界的原子

一個大於 $1$ 的整數，如果除了 $1$ 和它自己以外沒有其他正因數，就稱為質數（prime number）。前幾個質數是：

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ \dots$$

質數之所以重要，是因為算術基本定理（Fundamental Theorem of Arithmetic）：每個大於 $1$ 的整數都能唯一地分解成質數的乘積（不計順序）。例如：

$$360 = 2^3 \times 3^2 \times 5.$$

這個「唯一性」是整個數論的地基。質數就像化學裡的元素、物質裡的原子——所有整數都由它們組合而成。

質數有多少？

歐幾里得用一個漂亮到令人屏息的論證告訴我們：質數有無窮多個。假設質數只有有限個 $p_1, p_2, \dots, p_n$，考慮

$$N = p_1 p_2 \cdots p_n + 1.$$

這個 $N$ 除以任何一個 $p_i$ 都餘 $1$，所以它要嘛本身是新的質數，要嘛有不在清單中的質數因數——無論哪種情況，都與「質數有限」矛盾。於是質數必然無窮。

質數雖無窮，卻越來越「稀疏」。質數定理（Prime Number Theorem）精確描述了這種稀疏：不超過 $x$ 的質數個數 $\pi(x)$ 滿足

$$\pi(x) \sim \frac{x}{\ln x},$$

意思是當 $x$ 很大時，$\pi(x)$ 與 $x/\ln x$ 的比值趨近於 $1$。換句話說，在 $x$ 附近，一個隨機整數是質數的「機率」大約是 $1/\ln x$。

最大公因數與歐幾里得演算法

談同餘之前，先看一個古老又實用的工具。兩個整數 $a, b$ 的最大公因數（greatest common divisor）記作 $\gcd(a, b)$。如果 $\gcd(a,b) = 1$，我們說 $a$ 與 $b$ 互質（coprime）。

歐幾里得演算法利用一個簡單事實：$\gcd(a, b) = \gcd(b,\ a \bmod b)$，反覆取餘數直到餘數為 $0$。

看一個例子：求 gcd(252, 198)

$$ \begin{aligned} 252 &= 1 \times 198 + 54,\\ 198 &= 3 \times 54 + 36,\\ 54 &= 1 \times 36 + 18,\\ 36 &= 2 \times 18 + 0. \end{aligned} $$

最後一個非零餘數是 $18$，所以 $\gcd(252, 198) = 18$。整個過程只用了四步——即使數字大到上百位，這個演算法依然飛快，這正是它在密碼學中不可或缺的原因。

更進一步，貝祖定理（Bézout's identity）保證存在整數 $x, y$ 使得

$$ax + by = \gcd(a, b).$$

把上面的算式逆推（擴展歐幾里得演算法），就能找出這組係數。這組係數正是後面計算「模反元素」的關鍵。

同餘：時鐘上的算術

如果兩個整數 $a, b$ 除以正整數 $m$ 餘數相同，我們就說它們模 $m$ 同餘（congruent modulo $m$），記作：

$$a \equiv b \pmod{m}.$$

等價地，$m \mid (a - b)$（$m$ 整除 $a-b$）。最日常的例子就是時鐘：現在是 $10$ 點，再過 $5$ 小時是 $3$ 點，因為

$$10 + 5 = 15 \equiv 3 \pmod{12}.$$

同餘最迷人的地方在於：它和加法、減法、乘法完全相容。若 $a \equiv b \pmod m$ 且 $c \equiv d \pmod m$，則

$$a + c \equiv b + d \pmod m, \qquad ac \equiv bd \pmod m.$$

這代表我們可以先取餘數、再運算，大幅簡化巨大數字的計算。

動手試試：$7^{100}$ 的個位數是多少？

「個位數」其實就是「模 $10$ 的餘數」。我們觀察 $7$ 的次方模 $10$ 的循環：

$$ \begin{aligned} 7^1 &\equiv 7,\\ 7^2 &\equiv 49 \equiv 9,\\ 7^3 &\equiv 7 \times 9 = 63 \equiv 3,\\ 7^4 &\equiv 7 \times 3 = 21 \equiv 1 \pmod{10}. \end{aligned} $$

到 $7^4$ 又回到 $1$，所以週期是 $4$。因為 $100 = 4 \times 25$，

$$7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}.$$

$7^{100}$ 的個位數是 $\mathbf{1}$。注意：我們完全不需要算出那個有 $85$ 位數的龐然大物，同餘讓計算瞬間瓦解。

費馬小定理與歐拉定理

上面那個「週期 $4$」並非巧合。費馬小定理（Fermat's Little Theorem）指出：若 $p$ 是質數，且 $a$ 不被 $p$ 整除，則

$$a^{p-1} \equiv 1 \pmod{p}.$$

例如取 $p = 5,\ a = 3$：$3^4 = 81 = 16 \times 5 + 1 \equiv 1 \pmod 5$，果然成立。

當模數不是質數時，需要用到歐拉定理（Euler's theorem）。先定義歐拉函數（Euler's totient function） $\varphi(n)$，表示 $1$ 到 $n$ 之間與 $n$ 互質的整數個數。對於兩個相異質數 $p, q$ 的乘積 $n = pq$，有一個關鍵公式：

$$\varphi(pq) = (p-1)(q-1).$$

歐拉定理說：若 $\gcd(a, n) = 1$，則

$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

這條定理就是下一節 RSA 密碼系統能夠「加密後又解得回來」的數學心臟。

從同餘到密碼：RSA 的核心想法

現代公開金鑰密碼（public-key cryptography）建立在一個不對稱的事實上：

把兩個大質數相乘很容易，但把它們的乘積分解回去極其困難。

把兩個三百位的質數相乘，電腦一瞬間就完成；但給你那個六百位的乘積，要找回原本的兩個質數，即使動用全球的超級電腦也可能要算上數百萬年。RSA（以發明者 Rivest、Shamir、Adleman 命名）正是把這道鴻溝變成一把鎖。

RSA 的運作骨架如下：

1. 選兩個大質數 $p, q$，計算 $n = pq$ 與 $\varphi(n) = (p-1)(q-1)$。
2. 選一個與 $\varphi(n)$ 互質的公鑰指數 $e$。
3. 用擴展歐幾里得演算法求出私鑰指數 $d$，滿足 $ed \equiv 1 \pmod{\varphi(n)}$。
4. 公開 $(n, e)$，私藏 $d$。

加密訊息 $M$ 與解密密文 $C$ 分別為：

$$C \equiv M^e \pmod{n}, \qquad M \equiv C^d \pmod{n}.$$

為什麼解得回來？因為 $ed \equiv 1 \pmod{\varphi(n)}$，所以 $ed = 1 + k\varphi(n)$，於是由歐拉定理：

$$C^d \equiv M^{ed} = M^{1 + k\varphi(n)} = M \cdot \big(M^{\varphi(n)}\big)^k \equiv M \cdot 1^k = M \pmod{n}.$$

整個安全性的根基，就是「不知道 $p, q$ 就算不出 $\varphi(n)$，也就反推不出私鑰 $d$」。

看一個迷你 RSA 範例

為了看清機制，我們用小數字示範（真實系統會用幾百位的質數）。

取 $p = 5,\ q = 11$，則

$$n = 55, \qquad \varphi(n) = (5-1)(11-1) = 40.$$

選公鑰 $e = 3$（與 $40$ 互質）。求私鑰 $d$，需要 $3d \equiv 1 \pmod{40}$。試算可得 $d = 27$，因為 $3 \times 27 = 81 = 2 \times 40 + 1 \equiv 1 \pmod{40}$。

現在加密訊息 $M = 7$：

$$C \equiv 7^3 = 343 \pmod{55}.$$

由 $343 = 6 \times 55 + 13$，得 $C = 13$。

解密 $C = 13$，需要計算 $13^{27} \bmod 55$。直接算很可怕，但用同餘逐步降冪就輕鬆了：

$$ \begin{aligned} 13^2 &= 169 \equiv 4 \pmod{55},\\ 13^4 &\equiv 4^2 = 16 \pmod{55},\\ 13^8 &\equiv 16^2 = 256 \equiv 36 \pmod{55}. \end{aligned} $$

因為 $27 = 16 + 8 + 2 + 1$，

$$13^{27} \equiv 13^{16} \cdot 13^{8} \cdot 13^{2} \cdot 13^{1} \pmod{55}.$$

我們還需要 $13^{16} \equiv 36^2 = 1296 \equiv 26 \pmod{55}$。代入：

$$13^{27} \equiv 26 \times 36 \times 4 \times 13 \pmod{55}.$$

逐步化簡：$26 \times 36 = 936 \equiv 11$；$11 \times 4 = 44$；$44 \times 13 = 572 \equiv 7 \pmod{55}$。

於是解密結果 $M = 7$——正是我們一開始的訊息！這個「先升冪加密、再升冪解密、最後完美還原」的循環，全靠歐拉定理在背後撐著。順帶一提，上面這套「平方－相乘」的快速冪（fast exponentiation）技巧，正是讓 RSA 在實務上跑得動的另一塊基石。

重點回顧

• 質數是整數的原子：算術基本定理保證每個整數有唯一的質因數分解；歐幾里得證明了質數有無窮多個。
• 同餘是模 $m$ 的算術：$a \equiv b \pmod m$ 與加減乘相容，讓我們能「先取餘數再運算」，把巨大數字的計算瞬間縮小。
• 歐幾里得演算法又快又老：反覆取餘數即可求最大公因數，其擴展版本能找出貝祖係數與模反元素。
• 費馬小定理與歐拉定理：$a^{p-1} \equiv 1 \pmod p$ 與 $a^{\varphi(n)} \equiv 1 \pmod n$ 是冪運算在模算術中循環回 $1$ 的根本原因。
• RSA 把「易乘難分解」變成一把鎖：公鑰加密、私鑰解密，安全性來自大數分解的計算困難性。

深入探討（研究所視角）

從研究的高度回望，本文走過的路線其實是初等數論通往代數結構與計算複雜度的縮影。

代數結構的視角。 模 $n$ 的剩餘類在乘法下構成群 $(\mathbb{Z}/n\mathbb{Z})^\times$，其階恰為 $\varphi(n)$。歐拉定理只是拉格朗日定理（Lagrange's theorem）「元素的階整除群的階」在此群上的特例。當 $n = p$ 為質數時，$\mathbb{Z}/p\mathbb{Z}$ 升格為有限體（finite field） $\mathbb{F}_p$，這是編碼理論、橢圓曲線密碼（elliptic curve cryptography, ECC）與代數幾何的共同舞台。值得注意的是 $(\mathbb{Z}/p\mathbb{Z})^\times$ 是循環群，存在原根（primitive root），這正是 Diffie–Hellman 金鑰交換與 ElGamal 系統的根基。

計算複雜度的視角。 RSA 的安全性並非建立在「分解不可能」，而是「分解在多項式時間內目前做不到」。整數分解屬於 $\mathsf{NP} \cap \mathsf{co\text{-}NP}$，但是否在 $\mathsf{P}$ 中仍是開放問題；目前最佳的古典演算法是一般數體篩法（General Number Field Sieve），其時間複雜度為次指數的

$$\exp\!\Big(\big(\tfrac{64}{9}\big)^{1/3} (\ln n)^{1/3} (\ln \ln n)^{2/3}\Big).$$

相對地，質數判定（primality testing）卻是多項式時間可解的——2002 年的 AKS 演算法證明了 $\mathrm{PRIMES} \in \mathsf{P}$。這種「判斷是不是質數很快、找出質因數很慢」的不對稱，正是公鑰密碼學存在的理由。

量子的陰影與後量子的回應。 1994 年 Shor 演算法證明：量子電腦能在多項式時間內分解大整數並求解離散對數，這意味著一旦大規模容錯量子電腦成真，RSA 與 ECC 將同時崩解。學界因此轉向後量子密碼（post-quantum cryptography），改以格（lattice）上的最短向量問題、編碼理論的解碼問題等「量子也難」的問題為基礎；NIST 已於近年標準化 CRYSTALS-Kyber 等格密碼方案。

通往解析數論的橋。 質數分布的精細結構由黎曼ζ函數（Riemann zeta function） $\zeta(s) = \sum_{n=1}^\infty n^{-s}$ 掌控，其與質數的連結由歐拉乘積給出：

$$\zeta(s) = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}.$$

質數定理的誤差項、乃至千禧年大獎的黎曼猜想（Riemann Hypothesis）——所有非平凡零點都落在 $\mathrm{Re}(s) = \tfrac12$ 上——都直接決定了 $\pi(x)$ 逼近 $x/\ln x$ 的精度。從你手機上那把鎖，一路追問下去，最終會撞上這道懸宕了一百六十多年、與「質數究竟如何排列」息息相關的世紀謎題。這正是數論的魅力：最日常的應用與最深邃的未解之謎，共享同一套整數的語言。