一般數域篩法（GNFS）的真正數學結構

GNFS 的終極目標是找到 $X, Y$，使得 $X^2 \equiv Y^2 \pmod N$。為了達成這個目標，數學家們在 「現實的整數世界」 與 「代數體世界」 之間架起了一座橋樑。那座橋樑正是「同態映射」。

第一階段：連結世界的「同態映射（Homomorphism）」

1. 多項式的選定與根的定義

對於巨大的合成數 $N$，選擇某個整數 $m$ 與多項式 $f(x)$，使得 $f(m) \equiv 0 \pmod N$。（例如：將 $N$ 進行 $m$ 進制展開，並從其係數構造 $f(x)$。此時假設 $f(x)$ 在有理數域 $\mathbb{Q}$ 上是不可約的（無法再因式分解））。

接著，將方程式 $f(x) = 0$ 的其中一個「複數根」設為 $\alpha$。理所當然，$f(\alpha) = 0$。$\alpha$ 不是整數，而是包含根號或虛數的複雜數（代數數）。

2. 環（Ring）與同態映射的建構

在這裡，我們準備兩個數學上的「環（定義了加法與乘法的世界）」。

世界A： $\mathbb{Z}[\alpha]$ （包含 $\alpha$ 的代數整數環）這是一個由 $a + b\alpha + c\alpha^2 + \dots$ 這種形式構成的數字世界。
世界B： $\mathbb{Z}/N\mathbb{Z}$ （除以 $N$ 的餘數環）這是一個僅由 $0$ 到 $N-1$ 的整數構成的同餘（Modulo）世界。

在這裡，我們定義一個從世界A到世界B的映射 $\phi$。 $$\phi : \mathbb{Z}[\alpha] \to \mathbb{Z}/N\mathbb{Z}$$ $$\phi(\alpha) = m \pmod N$$

這個映射 $\phi$ 是一個神奇的操作，能將世界A中的變數 $\alpha$ 直接替換成世界B中的整數 $m$。這個 $\phi$ 具有極其強大的性質，稱為 「環同態映射（Ring Homomorphism）」 。同態指的是 「在不破壞加法與乘法結構的情況下，傳送到另一個世界」 的性質。也就是說，以下方程式成立：

$\phi(X \times Y) = \phi(X) \times \phi(Y)$
$\phi(X^2) = \phi(X)^2$

這意味著什麼呢？如果我們能在「世界A（$\alpha$的世界）」中，創造出某個複雜元素 $\gamma$ 的 「平方（$\gamma^2$）」 ，那麼即使使用 $\phi$ 將其傳送到「世界B（餘數世界）」， 它的平方形式 $\phi(\gamma)^2$ 依然會完美保留 。

第二階段：質因數分解的崩壞與「理想（Ideal）」的誕生

我們希望在世界A（$\mathbb{Z}[\alpha]$）中，收集許多適當的元素 $(a - b\alpha)$，並將它們相乘，創造出一個「完全平方（平方元）」。通常，我們會將收集到的 $(a - b\alpha)$ 分別進行「質因數分解」，並確保質數的指數全為偶數來組合（利用矩陣求解）以創造平方。

然而，在這裡，代數學令人絕望的高牆擋住了去路。 在像 $\mathbb{Z}[\alpha]$ 這樣的代數體世界中，國中學到的 「質因數分解的唯一性（任何數字都能唯一地表示為質數相乘）」崩壞了 。

（例如：在某個代數體的世界中，$6 = 2 \times 3$，但同時 $6 = (1+\sqrt{-5}) \times (1-\sqrt{-5})$，我們將無從得知哪個才是真正的質數）

如果質因數分解不唯一，那麼「計算質數個數以湊成偶數個」的解謎（篩法）在原理上便無法執行。

庫默爾與戴德金的救贖：「理想」

拯救這種崩壞的，是 19 世紀數學家創造的概念—— 「理想（Ideal：理想數）」 。藉由不考慮元素本身，而是考慮該元素生成的「倍數集合（理想）」，再次使得質因數分解成為可能。

在代數體的整數環 $\mathcal{O}_K$（包含 $\mathbb{Z}[\alpha]$ 更完整的環）中，即使元素無法唯一質因數分解，已經證明了 「理想必定能唯一地質因數分解為『質理想（$\mathfrak{p}$）』的乘積」 。

因此在 GNFS 中，我們不是分解元素 $(a - b\alpha)$ 本身，而是將其生成的 主理想 $\langle a - b\alpha \rangle$ 進行質理想分解 。

第三階段：範數（Norm）與兩種篩子（Sieve）

那麼，我們該如何知道理想 $\langle a - b\alpha \rangle$ 會被分解成哪些質理想呢？這時我們使用一個稱為 「範數（Norm）」 的函數。範數是將代數體的複雜元素轉換為「現實世界普通整數 $\mathbb{Z}$」的函數。

元素 $(a - b\alpha)$ 的範數，可透過簡單的多項式計算 $b^d f(a/b)$ 來求得（$d$ 為 $f(x)$ 的次數）。

根據代數定理，我們知道： 「如果某個理想的範數可以完全分解為較小的質數（平滑），那麼原來的理想也可以完全分解為較小的質理想」 。

因此，GNFS 針對大量的整數對 $(a, b)$，同時計算以下兩者，並只收集兩者皆成為「平滑數」的整數對。

有理篩（Rational Sieve） ： $a - bm$ （現實世界的值）
代數篩（Algebraic Sieve） ： $b^d f(a/b)$ （代數體世界的範數）

收集數千萬個兩者皆平滑的整數對 $(a, b)$，將理想的質因數分解數據（包含幾個質理想）作為巨大的矩陣（在 GF(2) 上的線性代數）來求解，找到一個整數對的集合 $S$，使得「相乘後所有質理想的指數皆為偶數」。

第四階段：阻擋在前的兩個「障礙」與理想類群

透過矩陣計算，我們知道將屬於集合 $S$ 的 $(a - b\alpha)$ 的理想全部相乘，會變成某個理想 $I$ 的平方。

$$\prod_{S} \langle a - b\alpha \rangle = I^2$$

然而，這還沒結束。GNFS 中最深奧、最困難的數學高牆就在這裡。

我們最終想要的，不是「理想的平方」，而是為了代入映射 $\phi$ 的 「元素的平方（$\gamma^2$）」 。變成理想的平方，並不代表元素本身也一定是平方。這裡存在著 兩個強烈的數學障礙（Obstruction） 。

障礙①：理想類群（Ideal Class Group）的高牆

理想 $I$ 未必是「由單一元素生成的理想（主理想）」。我們無法從非主理想的理想中，提取出具體的元素 $\gamma$。

這時登場的概念是 「理想類群（Class Group, $Cl_K$）」 。理想類群是用來衡量「該代數體世界中存在多少非主理想的理想（質因數分解的唯一性被破壞到什麼程度）」的群。即使 $\prod \langle a - b\alpha \rangle$ 變成了 $I^2$，如果 $I$ 在理想類群中不是單位元素（主理想），就無法將其拉回為元素的平方。

障礙②：單位群（Unit Group）的高牆

假設運氣好，$I$ 剛好是主理想 $\langle \gamma \rangle$ 吧。那麼，$\prod \langle a - b\alpha \rangle = \langle \gamma^2 \rangle$。你可能會想「太好了，元素也是平方了！」，但這可是大錯特錯。

理想（倍數的集合）相等，並不代表元素完全相等。這兩者之間必定會產生 「單位（Unit：倒數也是整數的數字。如 1 或 -1 等）」 的偏差。也就是說，實際的元素等式會變成這樣：

$$\prod_{S} (a - b\alpha) = u \cdot \gamma^2$$

（$u$ 為單位群 $U_K$ 的元素）

如果這個單位 $u$ 本身不是某個東西的平方（平方元），那麼左邊絕對無法成為「完美的元素平方」。

第五階段：阿德曼的魔法「二次特徵（Quadratic Characters）」

理想類群的障礙與單位群的障礙。這兩個障礙該如何克服呢？這裡登場的是由密碼學家雷納德·阿德曼（RSA中的"A"）等人引入的天才手法—— 「二次特徵（Quadratic Characters）」 。

為了判定「某個元素在代數體中是否為完全平方」，我們使用勒讓德符號（二次剩餘）的代數體版本。在剛才那個巨大的矩陣（為了將質理想個數湊成偶數的解謎）中，我們 偷偷加上了幾十個額外條件（行），要求「對某些特殊質理想 $\mathfrak{q}$ 的二次特徵也全都要是 $1$（偶數）」 。

當我們透過矩陣計算找到連這些額外條件都滿足的集合 $S$ 時，根據代數數論的深奧定理，保證 「理想類群的障礙和單位群的障礙，將以壓倒性的機率自然消滅」 。

於是，我們終於得到了真正的等式：

$$\prod_{S} (a - b\alpha) = \gamma^2$$

最終階段：世界的融合與密碼崩壞

拼圖的最後一塊終於拼上了。

【代數體世界（世界A）的元素】 $\gamma^2 = \prod (a - b\alpha)$ （我們使用平方根演算法求出 $\gamma$）

【現實世界（有理數世界）的元素】 $V^2 = \prod (a - bm)$ （因為這只是單純的整數相乘，可以正常求出平方根 $V$）

好了，我們一開始建造的魔法橋樑， 同態映射 $\phi$ 該上場了。我們利用 $\phi$（將 $\alpha$ 代入為 $m$ 的映射），將世界A的元素 $\gamma$ 傳送到世界B（除以 $N$ 的餘數世界）。

$$Y = \phi(\gamma) \pmod N$$

另一方面，我們將在現實世界中產生的 $V$，直接帶入餘數世界成為 $X$。

$$X = V \pmod N$$

由於同態映射「保留結構」的性質，在世界A中成立的平方關係，在世界B（模 $N$ 的世界）中也完美保留。此外，由於原來的整數對 $(a, b)$ 是以 $a - b\alpha$ 和 $a - bm$ 的形式對應生成的，這個 $X$ 和 $Y$ 在模 $N$ 的世界中將會碰撞，產生以下絕對的等式：

$$X^2 \equiv Y^2 \pmod N$$

剩下能做的，就是祈禱這對 $X$ 與 $Y$ 不是平凡解（$X \equiv \pm Y$），然後計算 $\gcd(X - Y, N)$ 。

如果是非平凡解，歐幾里得演算法會在 0.001 秒內跑完，將作為 RSA 密碼心臟的秘密質數 $p$ 和 $q$ 印在輸出畫面上。

這就是集現代數學精華於一身的 「一般數域篩法（GNFS）」的完整樣貌 。