原根、二次剩餘與離散對數：另一把數論之鎖

已知 $a$、$b$ 與 $g^x \bmod p$，為什麼算回 $x$ 卻像在大海撈針？

你在入門篇已經和質數、同餘、以及 RSA 那把「容易上鎖、難以解鎖」的數論之鎖打過照面。那把鎖的安全性，建立在一個非常具體的不對稱：把兩個質數相乘很快，但把乘積分解回去很慢。

但密碼學裡還有另一把鎖，運作邏輯完全不同。它不靠「分解難」，而靠「找指數難」。考慮一個質數 $p$ 與一個固定的底數 $g$。給你 $x$，計算

$$ y \equiv g^{x} \pmod{p} $$

只需要 $O(\log x)$ 次乘法（快速冪）。但反過來，給你 $y$ 要還原 $x$，目前沒有已知的有效率演算法——這就是離散對數問題（discrete logarithm problem, DLP）。Diffie–Hellman 金鑰交換、ElGamal、乃至整個橢圓曲線密碼學（ECC）都站在它的肩膀上。

要真正理解這把鎖為什麼難開，我們得走進入門篇沒有細談的領域：模 $p$ 乘法群的內部結構、原根（primitive root）、二次剩餘（quadratic residue），以及把這一切黏合起來的乘法函數。這篇文章就帶你深入這個「同餘世界的幾何」。

模 $p$ 的乘法群：一個被忽略的「圓」

入門篇把同餘當成「時鐘算術」，但更深刻的觀點是：模 $p$ 的非零餘數，在乘法之下構成一個群（group），記作 $(\mathbb{Z}/p\mathbb{Z})^{\times}$。

這個群有 $p-1$ 個元素：$\{1, 2, \dots, p-1\}$。它封閉於乘法（因為 $p$ 是質數，兩個非零數的乘積不會變成 $0$），每個元素都有反元素（這正是費馬小定理的推論：$a^{p-1}\equiv 1$，所以 $a\cdot a^{p-2}\equiv 1$）。

關鍵的深刻事實是：

$(\mathbb{Z}/p\mathbb{Z})^{\times}$ 是一個循環群（cyclic group）。

「循環」意思是，存在某個元素 $g$，它的各次方 $g^1, g^2, \dots, g^{p-1}$ 恰好把整個群跑過一遍，不重不漏。這個 $g$ 就叫做模 $p$ 的原根。

舉個例子，取 $p=7$，試試 $g=3$：

$$ 3^1=3,\quad 3^2=2,\quad 3^3=6,\quad 3^4=4,\quad 3^5=5,\quad 3^6=1 \pmod 7 $$

你看，$\{3,2,6,4,5,1\}$ 正好是 $\{1,2,3,4,5,6\}$ 的重排。所以 $3$ 是模 $7$ 的原根。換句話說，乘法群其實「長得像」一個有 $p-1$ 個刻度的圓——原根就是那根一步走一格、繞一圈剛好回到起點的指針。

這個「圓」的存在，正是離散對數有意義的前提：$y\equiv g^x$ 把指數 $x$（一個加法世界的量）對應到 $y$（一個乘法世界的量）。離散對數，就是這個對應的反函數。

看一個例子：用原根「翻譯」乘法為加法

延續 $p=7$、$g=3$。我們可以做一張「離散對數表」（也叫指標表，index table）：

有了這張表，模 $7$ 的乘法就退化成模 $6$ 的加法。例如算 $5\times 6 \pmod 7$：

$$ \log_3(5\times 6)\equiv \log_3 5+\log_3 6 = 5+3 = 8\equiv 2\pmod 6 $$

而 $\log_3$ 值為 $2$ 的是 $y=2$，所以 $5\times 6\equiv 2\pmod 7$。驗證：$5\times 6=30\equiv 2\pmod 7$。正確。

這正是對數的精神——把乘法變加法。差別只在於：實數的對數可以用級數連續逼近，而離散對數沒有「連續」可言，整張表彷彿被徹底打亂，看不出 $y$ 和 $\log_g y$ 之間有任何可利用的規律。難，就難在這裡。

二次剩餘：哪些數開得了平方根？

走進這個圓之後，一個自然的問題是：在模 $p$ 的世界裡，哪些數有平方根？

一個數 $a$（與 $p$ 互質）若存在 $x$ 使得 $x^2\equiv a\pmod p$，就稱 $a$ 為二次剩餘（quadratic residue, QR）；否則為二次非剩餘。

模 $7$ 時，把 $1$ 到 $6$ 平方看看：

$$ 1^2=1,\ 2^2=4,\ 3^2=2,\ 4^2=2,\ 5^2=4,\ 6^2=1 \pmod 7 $$

得到的集合是 $\{1,2,4\}$。所以模 $7$ 的二次剩餘恰好有三個，非剩餘 $\{3,5,6\}$ 也恰好三個。這不是巧合：對奇質數 $p$，二次剩餘和非剩餘永遠各佔一半，各 $\frac{p-1}{2}$ 個。

從循環群的視角看，原因一目了然。$a$ 是二次剩餘 $\iff$ $\log_g a$ 是偶數。因為 $x^2\equiv a$ 翻譯成指標就是 $2\log_g x\equiv \log_g a\pmod{p-1}$，而 $p-1$ 為偶數，這個方程有解的充要條件正是 $\log_g a$ 為偶數。圓上一半的刻度是偶數，一半是奇數——剛好對半分。

勒讓德符號與歐拉判別法

我們用勒讓德符號（Legendre symbol）簡潔地記錄這件事：

$$ \left(\frac{a}{p}\right)= \begin{cases} +1 & a \text{ 是二次剩餘}\\ -1 & a \text{ 是二次非剩餘}\\ 0 & p\mid a \end{cases} $$

歐拉判別法（Euler's criterion）給了它一個可計算的公式：

$$ \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p $$

直覺是這樣：由費馬小定理 $a^{p-1}\equiv 1$，所以 $a^{(p-1)/2}$ 是 $1$ 的平方根，只能是 $\pm 1$。若 $a=x^2$，則 $a^{(p-1)/2}=x^{p-1}\equiv 1$；若 $a$ 是非剩餘，恰好落到 $-1$。

驗證 $a=2$、$p=7$：$2^{3}=8\equiv 1\pmod 7$，所以 $\left(\frac{2}{7}\right)=+1$，$2$ 確實是剩餘（前面看到 $3^2\equiv 2$）。再驗 $a=3$：$3^3=27\equiv 6\equiv -1\pmod 7$，所以 $3$ 是非剩餘，與前面的清單吻合。

二次剩餘不是抽象遊戲。它是 Goldwasser–Micali 加密、Rabin 密碼系統、以及許多零知識證明協定的核心難題——「二次剩餘性問題（quadratic residuosity problem）」在合數模下被認為是困難的。

把結構黏起來：乘法函數與歐拉 $\varphi$

到目前為止我們都在單一質數 $p$ 上工作。但 RSA 的模數是 $n=pq$，一旦離開質數，循環群的漂亮結構就會碎裂、重組。負責描述這個重組的，是乘法函數（multiplicative function）。

一個算術函數 $f$ 若滿足：當 $\gcd(m,n)=1$ 時 $f(mn)=f(m)f(n)$，就稱為乘法函數。入門篇出現過的歐拉函數 $\varphi(n)$（小於 $n$ 且與 $n$ 互質的數的個數）正是其中最重要的一員：

$$ \varphi(p^k)=p^k-p^{k-1},\qquad \varphi(mn)=\varphi(m)\varphi(n)\ \ (\gcd(m,n)=1) $$

於是對 $n=\prod p_i^{k_i}$，

$$ \varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right) $$

乘法函數的威力在於：只要知道一個質數冪上的值，就能拼出所有合數上的值。 整個數論大廈很多時候就是這樣由質數「組裝」出來的。這也呼應了中國剩餘定理（CRT）的精神——$(\mathbb{Z}/n\mathbb{Z})^\times$ 在 $n=pq$ 時會「分解」成 $(\mathbb{Z}/p\mathbb{Z})^\times \times (\mathbb{Z}/q\mathbb{Z})^\times$ 的直積。

動手試試：莫比烏斯反演的一次體驗

乘法函數家族裡還有一位低調但極關鍵的成員：莫比烏斯函數（Möbius function） $\mu(n)$。

$$ \mu(n)= \begin{cases} 1 & n=1\\ (-1)^r & n \text{ 為 } r \text{ 個相異質數之積（無平方因子）}\\ 0 & n \text{ 含平方因子} \end{cases} $$

它的神奇之處在於這個求和恆等式：

$$ \sum_{d\mid n}\mu(d)= \begin{cases} 1 & n=1\\ 0 & n>1 \end{cases} $$

驗證 $n=12$：其因數 $1,2,3,4,6,12$，對應 $\mu$ 值為 $1,-1,-1,0,1,0$，總和 $=0$。成立。

這個「正負抵消」的性質讓我們能做莫比烏斯反演（Möbius inversion）：若 $g(n)=\sum_{d\mid n}f(d)$，則可反推

$$ f(n)=\sum_{d\mid n}\mu(d)\,g\!\left(\frac{n}{d}\right) $$

它就像離散版的微積分基本定理，把「累加」反過來變成「差分」。在計算質數計數函數、各種篩法、甚至物理的容斥問題中，它都是主力工具。試著用它驗證 $\sum_{d\mid n}\varphi(d)=n$ 的反演形式，你會親手摸到乘法函數彼此勾連的骨架。

攻擊離散對數：難，但不是無限難

回到開頭那把鎖。如果離散對數真的只能「查整張表」，那麼對 $p$ 大到 $2048$ 位元時根本不可行——表有 $2^{2048}$ 列。但聰明的演算法能把難度從「指數」壓到「平方根」級。

Baby-step Giant-step（小步大步法） 的核心觀念是把指數寫成 $x=im+j$，其中 $m=\lceil\sqrt{p-1}\,\rceil$。於是

$$ g^{x}=y \;\Longrightarrow\; g^{j}=y\,(g^{-m})^{i} $$

預先算好所有 $g^j$（$j=0,\dots,m-1$）存進雜湊表（baby steps），再逐一試 $y(g^{-m})^i$（giant steps）找碰撞。時間與空間都是 $O(\sqrt{p})$——對 $p\approx 10^{12}$ 來說，從一兆次降到一百萬次，是天壤之別。

這也是為什麼現代密碼學要求群階含有大質因數：若 $p-1$ 全是小質數之積（所謂 smooth），Pohlig–Hellman 演算法可以用 CRT 把問題拆到各個小質數子群上各個擊破，整把鎖瞬間崩潰。安全的參數必須讓 $p-1$ 至少有一個夠大的質因數。

重點回顧

• 乘法群是循環的：$(\mathbb{Z}/p\mathbb{Z})^{\times}$ 由原根 $g$ 生成，整個同餘乘法世界其實是一個 $p-1$ 刻度的「圓」，這是離散對數成立的舞台。
• 指標把乘法變加法：模 $p$ 的乘法 $\cong$ 模 $p-1$ 的加法，但這座橋（離散對數）目前沒有有效率的反向走法，正是 Diffie–Hellman 與 ECC 的安全根基。
• 二次剩餘對半分：$a$ 是二次剩餘 $\iff$ 其指標為偶數 $\iff a^{(p-1)/2}\equiv 1$（歐拉判別法）；勒讓德符號是記錄這件事的記號。
• 乘法函數從質數組裝合數：$\varphi$、$\mu$ 等函數只要知道質數冪上的值即可推得全部，莫比烏斯反演則是把「累加」反推回「原函數」的離散基本定理。
• 難度可被壓到平方根：BSGS 把離散對數從 $O(p)$ 降到 $O(\sqrt p)$；參數安全要求群階含大質因數，否則 Pohlig–Hellman 會把鎖拆碎。

深入探討（研究所視角）

把上述零件拉到研究所的高度，會看到三條彼此交織的主線。

其一：二次互反律與類域論的源頭。 勒讓德符號滿足高斯稱為「黃金定理」的二次互反律（quadratic reciprocity）：對相異奇質數 $p,q$，

$$ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} $$

這條看似關於平方根的恆等式，其實是類域論（class field theory） 的最初投影——它把「在 $\mathbb{Q}$ 上一個質數如何分裂」這件事，編碼成模算術的對稱性。Artin 互反律把它推廣為阿貝爾擴張的伽羅瓦群與 idèle 類群之間的同構，而 Langlands 綱領則進一步把非阿貝爾的情形與自守表示（automorphic representations）連結，是當代數論的中軸。

其二：解析數論與 $L$-函數。 莫比烏斯函數不只是組合工具。狄利克雷級數 $\sum_n \mu(n)n^{-s}=1/\zeta(s)$ 把 $\mu$ 直接綁到黎曼 $\zeta$ 函數上，而質數定理 $\pi(x)\sim x/\ln x$ 的證明，本質上等價於 $\zeta(s)$ 在 $\mathrm{Re}(s)=1$ 上無零點。黎曼猜想——所有非平凡零點都落在 $\mathrm{Re}(s)=\frac12$ 上——等價於對 $\sum_{n\le x}\mu(n)=O(x^{1/2+\varepsilon})$ 這樣的誤差界，也就是說 $\mu$ 的正負必須抵消得「幾乎像隨機」。乘法函數的均值行為（Halász、Granville–Soundararajan 理論）至今仍是活躍的研究前沿。

其三：從有限體到橢圓曲線。 把模 $p$ 的乘法群換成橢圓曲線上的有理點群 $E(\mathbb{F}_p)$，離散對數問題就升級為 ECDLP。它的群階由 Hasse 定理約束在 $p+1-2\sqrt p \le \#E(\mathbb{F}_p)\le p+1+2\sqrt p$，且至今沒有像數體篩法（NFS）那樣的次指數演算法可破——這正是 ECC 能用遠小的金鑰達到同等安全的原因。然而一旦 Shor 演算法在容錯量子電腦上落地，無論是整數分解、模 $p$ 離散對數還是 ECDLP，都會被多項式時間攻破。這把後量子密碼學（lattice-based、isogeny-based）推上檯面——其中 isogeny 路線（如 CSIDH）正是把「兩條橢圓曲線之間的同源映射」當成新的單向函數，可以說數論在密碼學裡的故事，又繞回了曲線與群的幾何。

如果你想動手探索，建議從 SageMath 或 Python 的 sympy 開始：用 n_order、primitive_root、legendre_symbol、discrete_log 親手量一量不同 $p$ 的乘法群結構，觀察 $p-1$ 的質因數分解如何決定一把鎖的真實強度。你會發現，所謂「安全」，從來不是一句口號，而是一道可以被計算、被驗證、被攻擊的數論不等式。