跳轉到

09.3 數論專題#

本節目標#

  • 學會用 isprime() 判質數、factorint() 做質因數分解、primepi() 數質數個數
  • 掌握模算術工具：mod_inverse、冪次取模 \(a^b \bmod m\)
  • 建立 RSA 加密的數學直覺，並用小質數完成一次完整的加解密實驗
  • 實驗：測量 SymPy 判斷大數是否為質數的速度

質數：isprime、factorint、primepi#

質數是數論的基石。SymPy 提供三個常用函數：

  • isprime(n)：判斷 \(n\) 是否為質數（先做小質數試除，再用 Miller–Rabin 等機率／確定性測試）
  • factorint(n)：回傳質因數分解的字典 {質因數: 次方}
  • primepi(n)：計算不超過 \(n\) 的質數個數，即質數計數函數 \(\pi(n)\)
from sympy import isprime, factorint, primepi

print(isprime(97))            # True
print(isprime(1))             # False（1 不是質數）
print(factorint(2024))        # {2: 3, 11: 1, 23: 1}，即 2^3 * 11 * 23
print(primepi(100))           # 25：100 以內有 25 個質數

其他順手的小工具：

from sympy import primerange, prime, nextprime

print(list(primerange(10, 30)))   # [11, 13, 17, 19, 23, 29]
print(prime(10))                  # 29：第 10 個質數
print(nextprime(100))             # 101

模算術：mod_inverse 與冪次取模#

模算術就是「只看餘數」的算術。記號 \(a \equiv b \pmod m\) 表示 \(a\) 與 \(b\) 除以 \(m\) 的餘數相同。

乘法反元素：在模 \(m\) 之下， \(a\) 的反元素 \(a^{-1}\) 滿足 \(a \cdot a^{-1} \equiv 1 \pmod m\) ，存在條件是 \(\gcd(a, m) = 1\) ：

from sympy import mod_inverse

print(mod_inverse(3, 11))     # 4，因為 3*4 = 12 ≡ 1 (mod 11)
print((3 * 4) % 11)           # 1，驗證
print(mod_inverse(6, 15))     # ValueError：gcd(6, 15) = 3 ≠ 1

冪次取模 \(a^b \bmod m\) 是密碼學的核心運算。Python 內建的 pow(a, b, m) 用「平方-乘」快速演算法，即使指數大如天文數字也瞬間完成：

print(pow(7, 1000, 13))       # 9：7^1000 mod 13
print(pow(2, 10**100, 97))    # 大指數也瞬間算完

# 費馬小定理：p 質數時 a^(p-1) ≡ 1 (mod p)
print(pow(7, 96, 97))         # 1

離散對數的直覺：冪次運算 \(a^b \bmod m\) 很容易（快速冪），但反過來「已知 \(a^b \bmod m\) 和 \(a\) ，求 \(b\) 」卻極難——這就是離散對數問題。這種「正向易、反向難」的不對稱性正是公鑰密碼學的基礎：

from sympy.ntheory.residue_ntheory import discrete_log

# 3^x ≡ 13 (mod 17)，x 是多少？（答案：x = 4，因為 3^4 = 81 ≡ 13）
print(discrete_log(17, 13, 3))   # 4
# 數字小時可以暴力找，數字一大就不可行了

RSA 的數學直覺#

RSA 建立在這個事實上：把兩個大質數相乘很容易，但把乘積分解回兩個質數極難。流程如下：

  1. 選兩個質數 \(p, q\) ，算 \(n = pq\) 與 \(\varphi(n) = (p-1)(q-1)\)
  2. 選 \(e\) 與 \(\varphi(n)\) 互質，公鑰是 \((e, n)\)
  3. 私鑰 \(d\) 是 \(e\) 在模 \(\varphi(n)\) 下的反元素： \(ed \equiv 1 \pmod{\varphi(n)}\)
  4. 加密： \(c = m^e \bmod n\) ；解密： \(m = c^d \bmod n\)

其正確性由尤拉定理 \(m^{\varphi(n)} \equiv 1 \pmod n\) 保證。動手做一個小例子：

from sympy import isprime, mod_inverse, randprime

# 1. 選兩個小質數
p, q = 61, 53
assert isprime(p) and isprime(q)

n = p * q
phi = (p - 1) * (q - 1)
print(f"n = {n}, phi(n) = {phi}")   # n = 3233, phi = 3120

# 2. 選公鑰指數 e（與 phi 互質）
e = 17
from sympy import gcd
print(gcd(e, phi))   # 1

# 3. 算私鑰 d：e 在模 phi 下的反元素
d = mod_inverse(e, phi)
print(f"d = {d}")    # 2753，因為 17*2753 = 46801 ≡ 1 (mod 3120)

# 4. 加密與解密：訊息 m 必須小於 n
m = 65   # 想傳的數字
c = pow(m, e, n)
print(f"密文 c = {c}")             # 2790
print(f"解密回 m = {pow(c, d, n)}") # 65，正確還原

再驗證一次完整往返，並用隨機大質數產生鑰匙：

for m in range(2, 10):
    c = pow(m, e, n)
    assert pow(c, d, n) == m
print("所有往返測試通過")

# 隨機產生兩個 100 位元左右的大質數
p2 = randprime(10**99, 10**100)
q2 = randprime(10**99, 10**100)
print(isprime(p2), isprime(q2))   # True True

注意：真的 RSA 會用數百位元的質數。攻擊者只知道 \(n\) 與 \(e\) ，要算 \(d\) 就必須先對 \(n\) 做質因數分解——目前沒有效率的演算法能對大數做到。

動手實驗：判斷大數是否質數的速度#

isprime 對多大的數還能瞬間回答？用 timeit 實測：

import time
from sympy import isprime, factorint, nextprime

# 先做出幾個大數：質數與質數乘積（半質數）
p = nextprime(10**20)
q = nextprime(10**21)
semiprime = p * q

for n in [97, 10**12 + 39, p, semiprime]:
    t0 = time.perf_counter()
    result = isprime(n)
    dt = time.perf_counter() - t0
    print(f"isprime({n}): {result}，耗時 {dt*1000:.3f} ms")

典型的輸出顯示：即使數字有 40 多位元數，isprime 也在幾毫秒內回答。接著對照組——質因數分解就慢多了：

t0 = time.perf_counter()
f = factorint(semiprime)
dt = time.perf_counter() - t0
print(f"factorint({semiprime}) = {f}，耗時 {dt:.4f} 秒")

實驗延伸：把 \(p, q\) 的位數從 20 位逐步加倍到 40、60 位，觀察 isprime 幾乎不變慢，但 factorint 的時間急速成長。這條「判質數容易、分解難」的鴻溝，就是 RSA 安全性的實證直覺。

小結與練習#

本節重點

  • isprime(n) 判質數、factorint(n) 質因數分解、primepi(n) 質數計數
  • mod_inverse(a, m) 求模反元素（存在條件 \(\gcd(a, m) = 1\) ）
  • pow(a, b, m) 快速計算 \(a^b \bmod m\) ；離散對數是其反問題，且極難
  • RSA：公鑰 \((e, n)\) 加密 \(m^e \bmod n\) ，私鑰 \(d = e^{-1} \bmod \varphi(n)\) 解密

練習

  1. 求 \(\pi(1000)\) ，並估計 \(\pi(n) \approx n / \ln n\) 在 \(n = 1000\) 時的誤差。
  2. 解同餘方程 \(7x \equiv 3 \pmod{26}\) （提示：用 mod_inverse）。
  3. 用質數 \(p = 101, q = 113\) 建 RSA 鑰匙對（自己選 \(e\) ），加密 \(m = 42\) 再解密驗證。
  4. 實驗：用 discrete_log 猜 \(2^x \bmod 101 = 1\) 的最小正整數 \(x\) ，並與費馬小定理的理論值 100 對照（提示：檢查所有因數）。