07.2 尤拉定理與費馬小定理：模運算的指數律#

0. 導言：從「乘 100 次」到「繞圈一圈」#

上一章我們建立了 \(\mathbb{Z}_m\) 的加法與乘法，但現實密碼學真正需要的是指數：RSA 的加密就是 \(c = m^e \bmod n\) ， \(e\) 可能是 65537， \(n\) 是 2048 位元的數。逐次相乘完全不可行。救星是三個跨越 250 年的定理：

• Fermat 小定理（1640，Fermat 在信中提出，Euler 1736 首次發表證明）；
• Euler 定理（1760 年代，Euler 推廣到合成數模數）；
• Euler \(\varphi\) 函數（衡量「與 \(m\) 互質的剩餘」有多少個）。

三者構成 07.3 中 RSA「加密後能解密回來」的完整數學根據。前因是 07.1 的消去律與 \(\mathbb{Z}_m\) 結構，後果是模指數演算法（平方-乘法）與公開金鑰密碼學。

驅動關係：Euler 想證明 Fermat 猜想 → 發現需要 \(\varphi(m)\) → 定理成立 → 200 年後 Rivest/Shamir/Adleman 發現 \(m^{ed} \equiv m \pmod n\) 恰好就是「加密再解密」。

1. 尤拉 \(\varphi\) 函數#

定義 1.1#

對 \(m \in \mathbb{Z}^+\) ，定義

即 \(1\) 到 \(m\) 之間與 \(m\) 互質的整數個數（也就是 \(\mathbb{Z}_m\) 中可逆元素的個數，記 \(\mathbb{Z}_m^*\) ）。

範例 1.2#

定理 1.3（ \(\varphi\) 的計算公式）#

1. \(\varphi(p) = p - 1\) （ \(p\) 為素數）。
2. \(\varphi(p^k) = p^k - p^{k-1} = p^k(1 - 1/p)\) 。
3. 若 \(\gcd(m, n) = 1\) ，則 \(\varphi(mn) = \varphi(m)\varphi(n)\) （ \(\varphi\) 是積性函數）。

證明：(1) 顯然。(2) 在 \(1..p^k\) 中，被 \(p\) 整除的恰有 \(p^{k-1}\) 個，其餘皆與 \(p^k\) 互質。(3) 比對 \(a \bmod m\) 與 \(a \bmod n\) ，由中國剩餘定理，這個對應是 \([0, mn)\) 與 \(\mathbb{Z}_m \times \mathbb{Z}_n\) 的一對一對應，且 \(\gcd(a, mn) = 1 \iff \gcd(a,m) = 1\) 且 \(\gcd(a,n) = 1\) ，故計數相乘。 \(\blacksquare\)

系理 1.4（一般公式）#

若 \(n = p_1^{e_1} \cdots p_k^{e_k}\) ，則

from sympy import factorint

def phi(n):
    result = n
    for p in factorint(n):        # 唯一分解
        result = result // p * (p - 1)
    return result

print([phi(m) for m in (1, 7, 8, 12, 15)])   # [1, 6, 4, 4, 8]
print(phi(2**10 * 3**5))                      # 2^9 * 2 * 3^4 * 2 = ...

RSA 視角：取 \(n = pq\) （兩大素數），則 \(\varphi(n) = (p-1)(q-1)\) 。知道 \(p, q\) 的人一秒算出 \(\varphi\) ；只知道 \(n\) 的人必須先分解 \(n\) ——這正是 RSA 的安全假設（見 07.3）。

2. 費馬小定理#

定理 2.1（Fermat 小定理，1640）#

設 \(p\) 為素數， \(a \in \mathbb{Z}\) ：

• 若 \(\gcd(a, p) = 1\) ，則 \(a^{p-1} \equiv 1 \pmod p\) ；
• 對任意 \(a\) ： \(a^{p} \equiv a \pmod p\) 。

證明（第一式，關鍵：利用消去律）。考慮集合

因 \(\gcd(a, p) = 1\) ，由 07.1 的消去律， \(ia \equiv ja \Rightarrow i \equiv j\) ，故 \(S\) 的 \(p-1\) 個元素兩兩相異，且皆不為 0，因此

兩邊全部相乘：

由 Wilson 定理 \((p-1)! \equiv -1 \pmod p\) （或直接由 \(\gcd((p-1)!, p) = 1\) ）與消去律，得 \(a^{p-1} \equiv 1 \pmod p\) 。第二式兩邊乘 \(a\) 即得（ \(\gcd(a,p)=1\) 時與第一式等價； \(p \mid a\) 時兩邊皆 \(\equiv 0\) ）。 \(\blacksquare\)

證明思想回顧：「乘以 \(a\) 」只是把 \(\{1, \dots, p-1\}\) 重新排列——這個「乘法作用是排列」的想法，正是 08.2 群作用與 Burnside 引理的胚芽。

範例 2.2#

\(2^{10} = 1024 \equiv 1 \pmod{11}\) ，因 \(2^{10} = 2^{11-1}\) 。驗證：

assert pow(2, 10, 11) == 1
assert pow(3, 100, 7) == pow(3, 100 % 6, 7)   # 指數可模 φ(p)=6 縮減
print(pow(3, 100, 7), pow(3, 4, 7))            # 4 4

Fermat 小定理的兩大用途#

1. 快速縮減指數： \(a^k \bmod p = a^{k \bmod (p-1)} \bmod p\) 。
2. 素數測試（機率式）：若存在 \(a\) 使 \(a^{n-1} \not\equiv 1 \pmod n\) ，則 \(n\) 一定不是素數（這是 07.1 Miller–Rabin 程式碼的理論核心）。

陷阱：逆命題不成立。Carmichael 數（如 \(561 = 3 \times 11 \times 17\) ）對所有與其互質的 \(a\) 都滿足 \(a^{n-1} \equiv 1\) ，卻是合成數。Euler 定理與更強的 Miller–Rabin 測試正是為了處理這種邊界情況。

3. 尤拉定理#

定理 3.1（Euler 定理，1760 年代）#

若 \(\gcd(a, m) = 1\) ，則

證明（與定理 2.1 完全同構，只是把 \(\{1,\dots,p-1\}\) 換成 \(\mathbb{Z}_m^*\) ）。令

為模 \(m\) 的縮剩餘系（即 \(\mathbb{Z}_m^*\) 的全部元素）。考慮 \(aR = \{ar_1, \dots, ar_{\varphi(m)}\}\) ：

1. 每個 \(ar_i\) 仍與 \(m\) 互質（ \(\gcd(ar_i, m) \mid \gcd(a,m) = 1\) 、 \(\gcd(r_i, m) = 1\) 的乘積性質）；
2. 兩兩相異： \(ar_i \equiv ar_j \Rightarrow r_i \equiv r_j\) （消去律）。

故 \(aR\) 也是一個縮剩餘系，其元素與 \(R\) 的元素模 \(m\) 依序相等（集合相等）。全部相乘：

而 \(\gcd(\prod r_i, m) = 1\) ，消去即得 \(a^{\varphi(m)} \equiv 1 \pmod m\) 。 \(\blacksquare\)

注意：取 \(m = p\) 時 \(\varphi(p) = p-1\) ，Euler 定理立即退回 Fermat 小定理。Fermat 是特例，Euler 是推廣——這是數學中「發現特例 → 抽象出正確概念（ \(\varphi\) ）→ 定理自動推廣」的典型劇本。

系理 3.2（指數縮減律）#

若 \(\gcd(a, m) = 1\) ，則

這條系理就是模指數能「秒算」的原因。

4. 模指數演算法：平方-乘法#

定理保證了指數可以縮減，但計算 \(a^k \bmod m\) 本身仍需高效演算法。平方-乘法（square-and-multiply）利用 \(k\) 的二進位表示：

其中 \(a^{2^{i+1}} = (a^{2^i})^2\) 。只需 \(O(\log k)\) 次乘法。

def mod_exp(a, k, m):
    """a^k mod m，O(log k) 次乘法（Python 的 pow(a,k,m) 內建即此演算法）"""
    result, base = 1, a % m
    while k > 0:
        if k & 1:                 # 這一位是 1 → 乘進結果
            result = (result * base) % m
        base = (base * base) % m  # 平方
        k >>= 1
    return result

# 例：計算 7^644 mod 645（教科書經典例題）
print(mod_exp(7, 644, 645), pow(7, 644, 645))   # 436 436

# 用 Euler 定理驗證指數縮減：φ(645) = φ(3)φ(5)φ(43) = 2*4*42 = 336
# 644 = 336 + 308
print(mod_exp(7, 644, 645), mod_exp(7, 308, 645))  # 436 436

複雜度對比： \(k\) 為 2048 位元時，直接相乘需 \(2^{2048}\) 次乘法（宇宙不可能），平方-乘法只需約 3072 次模乘（毫秒級）。沒有這個演算法，就沒有實用的 RSA。

5. 逆元素與RSA 的數學核心（預告）#

定理 5.1（模逆元素存在性）#

\(a\) 在 \(\mathbb{Z}_m\) 中有乘法反元素 \(\iff \gcd(a, m) = 1\) 。

證明：由 07.1 Bézout， \(\gcd(a,m)=1 \iff \exists x: ax \equiv 1 \pmod m\) 。且 Euler 定理給出明確公式： \(a^{-1} \equiv a^{\varphi(m)-1} \pmod m\) 。 \(\blacksquare\)

為什麼 RSA 一定解得回來？（證明在 07.3 完整給出）#

RSA 取 \(n = pq\) 、 \(\gcd(e, \varphi(n)) = 1\) ，選 \(d\) 使 \(ed \equiv 1 \pmod{\varphi(n)}\) 。對任意訊息 \(m\) （ \(\gcd(m, n) = 1\) ）：

一行的計算，背後是 Euler 1760 年的定理。數學理論比應用早了兩百年——這是「前因後果」最壯觀的例子。

# 完整的小型 RSA 流程（僅教學用，實務需 2048+ 位元）
from sympy import nextprime
import random

p, q = nextprime(10**6 + random.randint(0, 999)), nextprime(2 * 10**6 + random.randint(0, 999))
n, ph = p * q, (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, ph)                     # 擴展歐幾里得求反元素

m = 123456
c = pow(m, e, n)                       # 加密
m2 = pow(c, d, n)                      # 解密
print(p, q, n, ph)
print(c, m2, m2 == m)                  # True：Euler 定理保證的結果

6. 離散對數的伏筆#

Fermat/Euler 定理還揭示另一個單向結構：在 \(\mathbb{Z}_p^*\) 中（ \(p\) 素數），由 \(g\) 反覆自乘可以很快算出 \(g^x \bmod p\) （平方-乘法），但反過來由 \(g^x\) 求 \(x\) （離散對數問題）目前沒有多項式時間演算法。Diffie–Hellman（1976）的金鑰交換正是建立在其單向性上：

• Alice 送 \(A = g^a \bmod p\) ，Bob 送 \(B = g^b \bmod p\) ；
• 兩人分別算 \(B^a\) 、 \(A^b\) ，得共享祕密 \(g^{ab} \bmod p\) ；
• 偷聽者只看到 \(g, A, B\) ，求 \(g^{ab}\) 被相信等同於解離散對數。

07.3 將完整推導並分析其安全性。

7. 章末小結#

核心因果鏈： \(\mathbb{Z}_m^*\) （07.1）→ 「乘 \(a\) 是排列」→ Euler 定理 → 指數縮減 + 模逆元素 → RSA/Diffie–Hellman 的數學根據。「乘法作用是排列」這個證明技巧，將在 08.2 以群作用與 Burnside 引理的姿態正式登場。

8. 下一步#

本章的定理已經完整到足以推出 RSA 的正確性。下一章 07.3 RSA 與 Diffie–Hellman 將把這些零件組裝成改變世界的兩個協定：1976 年 Diffie–Hellman 如何用離散對數解決「金鑰分配問題」，1977 年 Rivest–Shamir–Adleman 如何用大數分解的困難性做出第一個可簽章的公開金鑰系統——並討論量子計算對它們的威脅。