一般数体篩法（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つの「障害」とイデアル類群

\[\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乗だ！」と思うかもしれませんが、大間違いです。

\[\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\) が求まります）

\[Y = \phi(\gamma) \pmod N\]\[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）」の完全な姿 です。