インターネットの暗号を破る人類最強の数学「一般数体篩法（GNFS）」とは？

私たちが毎日使っているインターネット。LINEのメッセージやYouTube、Amazonでの買い物など、すべての通信は「暗号」によって守られています。現在、世界中で最も使われている暗号の代表が「RSA暗号」です。

RSA暗号の守りの要（かなめ）は、非常にシンプルです。それは 「巨大な数の素因数分解は、コンピュータでも解けない」 という数学の性質を利用していること。たとえば、「15」なら「3 × 5」とすぐに分かりますが、これが「270桁の数字」になった瞬間、世界中のスーパーコンピュータを束ねても解くのに数億年かかってしまいます。

しかし、数学者たちも黙ってはいません。この鉄壁の暗号を打ち破るために、人類は 「一般数体篩法（GNFS：General Number Field Sieve）」 という、魔法のようなアルゴリズム（計算手順）を生み出しました。

この記事では、専門用語を一切使わず、 中学校で習う数学（素因数分解、文字式、最大公約数） の知識だけで、この「人類最強のアルゴリズム」が暗号を破るカラクリをステップごとに完全解説します！

第1章：暗号解読のゴールは「中学3年の公式」

巨大な素因数分解に立ち向かうための最大の必殺技。それは、中学3年生で習うこの公式です。

$X^2 - Y^2 = (X + Y)(X - Y)$

「えっ、こんな基礎的な公式で暗号が破れるの？」と思うかもしれません。しかし、これこそがすべてを解き明かすマスターキーなのです。

暗号を破るための最大の目標は、巨大な数 $N$ に対して、 「$X^2$ と $Y^2$ を $N$ で割った余りが同じになる数（$X$ と $Y$）」 を見つけることです。

なぜ「余りが同じ」だと暗号が解けるのか？

ある2つの数、$X^2$ と $Y^2$ の「$N$ で割った余りが同じ」だとします。余りが同じということは、 引き算をした「$X^2 - Y^2$」は、必ず $N$ でピッタリ割り切れる（$N$ の倍数になる） という法則があります。

ここで、暗号に使われる巨大な数 $N$ は、2つの秘密の素数（$p$ と $q$）の掛け算でできているとしましょう（$N = p \times q$）。

$X^2 - Y^2$ を因数分解すると $(X - Y)(X + Y)$ になります。これが $N$ の倍数であるということは、この掛け算のどこかに、秘密の素数 $p$ と $q$ が隠れているということです。

ここで奇跡が起きます。 2つの素数 $p$ と $q$ が、 「$p$ は $(X - Y)$ の部屋へ」「$q$ は $(X + Y)$ の部屋へ」 と、別々の部屋に分かれて入ってくれる確率が、数学的に 50%（2分の1） あるのです。

素数 $p$ だけが $(X - Y)$ の部屋に入った状態で、$(X - Y)$ と $N$ の 「最大公約数（共通する一番大きな部品）」 を計算してみましょう。

$(X - Y)$ の中身＝ $p \times$ 何かの数
$N$ の中身＝ $p \times q$ 共通している部品は 「$p$」 しかありませんよね！

つまり、最大公約数を計算した瞬間、隠れていた素数 $p$ がポロッとこぼれ落ち、暗号が完全に解読されてしまうのです。（※最大公約数は「ユークリッドの互除法」を使えば、スマホでも一瞬で計算できます）

【ちょっとコラム：なぜ2乗なの？3乗や2倍じゃダメ？】

「$2X - 2Y$」だと $2(X - Y)$ になり、部屋が1つしかないので素数を引き離せません。「$X^3 - Y^3$」だと部屋の大きさがアンバランスになり、計算がムダに重くなります。素数を2つに引き離すには、美しく2つの部屋に分かれる「2乗」が一番コスパが良いのです。

第2章：XとYをどう探す？「素数カード集めパズル」

ゴールは分かりました。しかし、「余りが同じになる $X^2$ と $Y^2$」を当てずっぽうで探しても、宇宙の寿命が終わるまで見つかりません。そこで、数学者たちは 「素数カード集めパズル」 という天才的な方法を思いつきました。

Step 1：砂金（滑らかな数）だけをザルで集める

まず、適当な数 $Z$ を用意し、2乗して $N$ で割った余り $W$ を計算します。（$Z^2 = W$ の余りの世界）

出てきた余り $W$ を素因数分解します。ここで、 「2, 3, 5, 7などの小さな素数だけでできている $W$」 が出たときだけ、その式を「アタリのカード」として残し、大きな素数が混ざっていたら捨てます。川で大きな石をザル（ふるい）で捨てて、砂金だけを集めるような作業です。

Step 2：全部「偶数個」にするパズル

たとえば、以下の3枚の砂金カードが集まったとします。

カードA： $Z_1^2 = 2^3 \times 3^1$
カードB： $Z_2^2 = 2^1 \times 5^1$
カードC： $Z_3^2 = 3^1 \times 5^1$

これを全部掛け合わせてみましょう。右側は $(2^3 \times 3^1) \times (2^1 \times 5^1) \times (3^1 \times 5^1)$ となり、まとめて整理すると 「$2^4 \times 3^2 \times 5^2$」 になります。

なんと、素数の個数が「4個、2個、2個」と、 すべて偶数個 になりました！すべて偶数個ということは、全体を半分の個数にすれば「何かの2乗」になります。つまり、$(2^2 \times 3^1 \times 5^1)^2 = (60)^2$ です。

左側は $(Z_1 \times Z_2 \times Z_3)^2$ なので、これでついに、 $X = (Z_1 \times Z_2 \times Z_3)$ $Y = 60$ という、待ちに待った「$X^2 = Y^2$」のペアが完成したのです！

コンピュータにとって、素数の個数を「偶数か奇数か（0か1か）」で計算するパズルは非常に得意なので、この方法なら高速に $X$ と $Y$ を見つけることができます。

第3章：立ちはだかる絶望の壁

これでどんな暗号も解ける！……と思いきや、大問題が発生します。暗号の数字 $N$ が「100桁」くらいまでならこの方法（二次篩法といいます）で解けるのですが、$N$ が「200桁、300桁」になると、計算の途中で出てくる $W$ がデカくなりすぎます。

数字がデカすぎると、「小さな素数だけでできている数（砂金）」がパッタリと出なくなってしまいます。砂漠でコンタクトレンズを探すよりも難しくなり、パズルを解くためのカードが全く集まらなくなってしまうのです。

ここでついに、人類の最終兵器 「一般数体篩法（GNFS）」 が登場します。

第4章：人類最強のアイディア「2つの世界」を作る

GNFSの天才的な発想は、 「現実の世界だけで計算するから数字がデカくなる。なら、多項式（文字式）を使った『裏の世界』を作って、計算の重さを2つに分散させよう」 というものです。

文字式の魔法

GNFSは、巨大な数 $N$ をベースとなる数 $m$ を使って、文字式に変換します。たとえば $N=100$ なら、$m=4$ として $100 = 4^3 + 2(4^2) + 4$。これを文字 $x$ を使って $f(x) = x^3 + 2x^2 + x$ という式（裏の世界）にします。

この式の面白いところは、 「文字 $x$ に $m$（上の例なら4）を代入すれば、いつでも現実の数 $N$ にワープして戻ってこれる」 という性質を持っていることです。

2つの世界で同時に砂金探し

GNFSは、適当な整数のペア $(a, b)$ をたくさん作り、次の2つの計算を同時に行います。

現実の世界： $a - b \times m$
文字式の世界： $a - b \times x$ を文字式のルールで計算した値

問題を2つの世界に分けたことで、扱う数字のサイズが劇的に小さく（軽く）なります。巨大な岩を2つに割って、扱いやすい石コロにしたイメージです。

そして、 「現実の世界でも、文字式の世界でも、両方とも『小さな素数だけでできている（砂金）』」 という奇跡のペア $(a, b)$ だけをザル（篩：ふるい）でより分けて集めます。これが「数体篩法」という名前の由来です。

ついに暗号が破れる瞬間

両方の世界から数千万枚の「砂金カード」が集まったら、スーパーコンピュータの巨大な行列計算を使って、第2章でやった「素数の個数が全部偶数になる組み合わせ」を見つけ出します。

組み合わせが見つかったら、

現実の世界でできた2乗の数を $X^2$
文字式の世界でできた2乗の式を $Y(x)^2$ とします。

最後に、文字式の $Y(x)$ の $x$ に $m$ を代入し、現実の世界にワープさせて合流させます。すると、数学の魔法のように 「$X^2$ と $Y^2$ の余りが同じになる」 という状態が厳密に完成するのです！

あとは第1章の通り、$X - Y$ と $N$ の最大公約数を計算すれば、難攻不落のRSA暗号は音を立てて崩れ去り、秘密の素数が姿を現します。

おわりに：数学は終わらない

「よし、GNFSを使えばどんな暗号も破れるんだな！」と思ったかもしれません。しかし、RSA暗号も負けていません。現在のインターネットで使われているのは「RSA-2048（約617桁）」というバケモノのような巨大数です。

GNFSがいかに人類最強のアルゴリズムとはいえ、270桁（RSA-270）を解くのにすら、世界中のコンピュータを繋いでも数千年、数万年かかると言われています。今のところ、私たちのLINEや銀行のデータは安全です。

しかし、もし 「どんな巨大な数でも一瞬で $X$ と $Y$ を見つける魔法」 が現れたらどうなるでしょうか？実は、それに最も近い存在が現在開発中の 「量子コンピュータ（ショアのアルゴリズム）」 です。量子力学の波の性質を使えば、面倒なカード集めパズルを無視して、一発で答えを引き当てることができると数学的に証明されています。

暗号を作る人（防御）と、暗号を破るアルゴリズムを作る人（攻撃）の果てしない知恵比べ。中学校で習う「素因数分解」や「文字式」が、実は世界のセキュリティの最前線でバチバチに戦っている武器だと知ると、少しだけ数学の授業が面白く見えてきませんか？

未来の最強アルゴリズムを発見するのは、この記事を読んでいるあなたかもしれません！

(※本記事は、暗号解読の数学的魅力を中学生向けに概念化したものです。実際のGNFSは、代数体のイデアル類群や準同型写像などの高度な大学数学を用いて厳密に計算されています)