一般數域篩法（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\)，使得「相乘後所有質理想的指數皆為偶數」。

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

\[\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\)。你可能會想「太好了，元素也是平方了！」，但這可是大錯特錯。

\[\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\)）

\[Y = \phi(\gamma) \pmod N\]\[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）」的完整樣貌 。