一般数体篩法（GNFS）の真の数学的構造

GNFSの究極の目的は、$X^2 \equiv Y^2 \pmod N$ となる $X, Y$ を見つけることです。これを達成するために、数学者たちは 「現実の整数の世界」 と 「代数体の世界」 の間に橋を架けました。その橋こそが「準同型写像」です。

第1段階：世界を繋ぐ「準同型写像（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）と準同型写像の構築

ここで、2つの数学的な「環（足し算と掛け算が定義された世界）」を用意します。

世界A： $\mathbb{Z}[\alpha]$ （$\alpha$ を含む代数的な整数の環） $a + b\alpha + c\alpha^2 + \dots$ という形で表される数の世界です。
世界B： $\mathbb{Z}/N\mathbb{Z}$ （$N$ で割った余りの環） $0$ から $N-1$ までの整数だけで構成される、合同式（モジュロ）の世界です。

ここで、世界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$ の 「2乗（$\gamma^2$）」 を作ることができれば、それを $\phi$ で「世界B（余りの世界）」にワープさせても、 見事に2乗の形 $\phi(\gamma)^2$ が保たれる ということです。

第2段階：素因数分解の崩壊と「イデアル（Ideal）」の誕生

私たちは世界A（$\mathbb{Z}[\alpha]$）の中で、適当な要素 $(a - b\alpha)$ をたくさん集め、それらを掛け合わせて「完全な2乗（平方元）」を作りたいと考えます。普通なら、集めた $(a - b\alpha)$ をそれぞれ「素因数分解」して、素数の指数がすべて偶数になるように組み合わせ（行列で解く）れば2乗が作れます。

しかし、ここで代数学の絶望的な壁が立ちはだかります。 $\mathbb{Z}[\alpha]$ のような代数体の世界では、中学で習う 「素因数分解の一意性（どんな数も素数の掛け算でただ1通りに表せる）」が崩壊してしまう のです。

（例：ある代数体の世界では、$6 = 2 \times 3$ であり、同時に $6 = (1+\sqrt{-5}) \times (1-\sqrt{-5})$ となってしまい、どちらが本当の素数か分からなくなります）

素因数分解が1通りに定まらなければ、「素数の個数を数えて偶数個にする」というパズル（篩法）が原理的に実行できません。

クンマーとデデキントの救済：「イデアル」

この崩壊を救ったのが、19世紀の数学者が生み出した 「イデアル（Ideal：理想数）」 という概念です。要素そのものではなく、その要素が生成する「倍数の集合（イデアル）」を考えることで、再び素因数分解を可能にしたのです。

代数体の整数環 $\mathcal{O}_K$（$\mathbb{Z}[\alpha]$ を含むより完全な環）において、要素は一意に素因数分解できなくても、 「イデアルは必ず『素イデアル（$\mathfrak{p}$）』の積としてただ1通りに素因数分解できる」 ことが証明されています。

したがってGNFSでは、要素 $(a - b\alpha)$ そのものを分解するのではなく、それが生成する 単項イデアル $\langle a - b\alpha \rangle$ を素イデアル分解 します。

第3段階：ノルム（Norm）と2つの篩（Sieve）

では、イデアル $\langle a - b\alpha \rangle$ がどんな素イデアルに分解されるか、どうやって知るのでしょうか？ここで 「ノルム（Norm）」 という関数を使います。ノルムとは、代数体の複雑な要素を「普通の現実の整数 $\mathbb{Z}$」に変換する関数です。

要素 $(a - b\alpha)$ のノルムは、$b^d f(a/b)$ という簡単な多項式の計算で求まります（$d$ は $f(x)$ の次数）。

代数的な定理により、 「あるイデアルのノルムが小さな素数で完全に分解できる（滑らかである）ならば、その元のイデアルも小さな素イデアルで完全に分解できる」 ことが分かっています。

そこでGNFSは、大量の整数のペア $(a, b)$ に対して、次の2つを同時に計算し、両方が「滑らかな数」になるペアだけを収集します。

有理篩（Rational Sieve）： $a - bm$ （現実の世界の値）
代数篩（Algebraic Sieve）： $b^d f(a/b)$ （代数体の世界でのノルム）

両方が滑らかなペア $(a, b)$ を数千万個集め、イデアルの素因数分解データ（素イデアルが何個含まれているか）を巨大な行列（GF(2)上の線形代数）として解き、「掛け合わせると全ての素イデアルの指数が偶数になる」ようなペアの集合 $S$ を見つけます。

第4段階：立ちはだかる2つの「障害」とイデアル類群

行列計算により、集合 $S$ に属する $(a - b\alpha)$ のイデアルをすべて掛け合わせると、あるイデアル $I$ の2乗になることが分かりました。

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

しかし、まだ終わりません。GNFSにおける最も深く、最も困難な数学の壁がここにあります。

私たちが最後に欲しいのは、「イデアルの2乗」ではなく、写像 $\phi$ に代入するための 「要素の2乗（$\gamma^2$）」 です。イデアルの2乗になったからといって、要素自体が2乗になっているとは限らないのです。ここには 2つの強烈な数学的障害（Obstruction） が存在します。

障害①：イデアル類群（Ideal Class Group）の壁

イデアル $I$ は、必ずしも「1つの要素で生成されるイデアル（単項イデアル）」とは限りません。単項イデアルではないイデアルから、具体的な要素 $\gamma$ を取り出すことは不可能です。

ここで 「イデアル類群（Class Group, $Cl_K$）」 という概念が登場します。イデアル類群とは、「その代数体の世界に、単項イデアルではないイデアルがどれくらい存在するか（素因数分解の一意性がどれくらい壊れているか）」を測る群です。 $\prod \langle a - b\alpha \rangle$ が $I^2$ になったとしても、$I$ がイデアル類群において単位元（単項イデアル）でなければ、要素の2乗に引き戻すことができません。

障害②：単数群（Unit Group）の壁

仮に運良く $I$ が単項イデアル $\langle \gamma \rangle$ だったとしましょう。すると、$\prod \langle a - b\alpha \rangle = \langle \gamma^2 \rangle$ となります。「よし、要素も2乗だ！」と思うかもしれませんが、大間違いです。

イデアル（倍数の集合）が等しいということは、要素が完全に等しいことを意味しません。必ず 「単数（Unit：逆数も整数になるような数。1 や -1 など）」 のズレが生じます。つまり、実際の要素の等式は次のようになります。

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

（$u$ は単数群 $U_K$ の要素）

この単数 $u$ 自体が何かの2乗（平方元）でなければ、左辺は絶対に「完全な要素の2乗」にはなれません。

第5段階：アドレマンの魔法「平方剰余指標（Quadratic Characters）」

イデアル類群の障害と、単数群の障害。この2つをどうやって乗り越えるのか？ここで、暗号学者レナード・アドレマン（RSAの"A"）らが導入した天才的な手法 「平方剰余指標（Quadratic Characters）」 が登場します。

「ある要素が代数体の中で完全に2乗になっているか？」を判定するために、ルジャンドル記号（平方剰余）の代数体バージョンを使います。先ほどの巨大な行列（素イデアルの個数を偶数にするためのパズル）に、「いくつかの特別な素イデアル $\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$ の出番です。世界Aの要素 $\gamma$ を、$\phi$（$\alpha$ に $m$ を代入する写像）を使って、世界B（$N$の余りの世界）にワープさせます。

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

一方、現実の世界で作った $V$ を、そのまま余りの世界に持っていき $X$ とします。

$$X = V \pmod N$$

準同型写像の「構造を保つ」性質により、世界Aで成り立っていた2乗の関係は、世界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）」の完全な姿 です。