AIエージェントが4日でRSA-260の数学难题を解いた

RSA-260、AIエージェントが4日で突破

RSA-260は公開問題リストに6年間放置されていたが、DevinというAIエージェントによって突破された。

RSA素因数分解チャレンジは公開されている問題リストで、数字の桁数によって難易度が分かれている。2020年2月にRSA-250が解かれ、公開記録は250桁に更新された。ひとつ上のランクのRSA-260は260桁（862ビット）の合成数で、1991年からずっと未解決のまま残されていた。

CognitionのエンジニアEric Luは9月3日、X上に「130桁の整数」と「RSA-260を割り切る」とだけ投稿した。6日後、完全な技術報告を公開した。

大数を分解する中核アルゴリズムはGNFS（一般数体篩法（General Number Field Sieve）。現在、大整数分解において最も効率的な古典アルゴリズムで、量子計算の要素は含まれない）だ。Devinが書いたのは新しいアルゴリズムではなく、高性能なGPU実装である。INRIAがオープンソースで公開しているCADO-NFSを改変し、元々CPUで走っていた格子篩（lattice sieving。GNFSの中で最も計算資源を消費する工程）をGPUで実行できるようにした。工学的な最適化によるものであり、数論上のブレークスルーではない。4日間で完走したこの結果は、6年間未解決だった公開問題が初めて解かれたことを意味する。

Luは記事の中でさらに試算も示している：スーパーコンピュータベンダーや最先端AI研究所がこのパイプラインを使ってRSA-1024（309桁）を分解すると、現在の市場価格で約3,000万ドルかかるという。RSA-2048（617桁、つまり現実世界で使われているRSA鍵長）はRSA-1024より約10億倍難しく、GNFSのアプローチではほぼ手出しできない。

コードはDevinが書き、性能測定はDevinがやり、クラスタはDevinが調整した

GNFSの3大工程は変わっていない。変わったのはコードを書く側だけで、研究者から1人のオペレーターとDevinの一団に変わった。

GNFS（一般数体篩法）による分解は3つの工程からなる：まず多項式を選び、次に格子篩（大量の候補関係式から大きな行列を構成する）を実行し、最後に疎な連立一次方程式を解く。Luはアルゴリズム自体を改変していない——彼はオープンソースのCADO-NFSを書き換え、最も計算資源を消費する格子篩工程をCPUからGPUに移し、交換可能な実装に作り替えて組み込んだ。

Luの役割は3つだけだった。優先順位を決めること、ベンチマークを策定すること、方向がブレていないかを認識すること。測定、クラスタスケジューリング、性能最適化（コードをより高速に、少ないリソースで動かすこと）はすべてDevinが自力で実行した。複数の報道で繰り返し出てくる詳細として、Luは1人で最大18のDevinセッションを同時に動かし、期間は約3週間だった。

クラスタは既存のものを流用した：NVL72ラック内で大規模モデルの訓練・推論の合間に余る断片的な計算資源だ。Cognitionはクラスタスケジューラを「これらの空き枠を拾い集める」用途で元々最適化しており、 RSA-260もその枠にうまく流し込んで実行した。パイプライン全体はクラスタの「1桁%」の計算資源しか占有しておらず、 LLMの訓練・推論以外で空いている単一ノードの断片だけで動いている。

これまでの記録との本質的な違いはアルゴリズムではなく、ボトルネックが移ったことだ——「人間がどれだけ速くコードを書けるか」から「いくつのDevinセッションを並列で動かせるか」へ。

1024ビットRSAが安全でないという話は、実は20年前から囁かれていた

人々が最も恐れる「AIが1024ビット暗号を壊した」という話は今回の新しいストーリーではない。本当の変化は、実行のハードルが下がったことだ。

Eric Luの主張を先に置こう：

この数字は唐突に出てきたものではない。TWIRLデバイスやバーンシュタインの行列マシン——1024ビット分解専用に設計されたニッチなハードウェアは、20年前からささやかれていた。Luが今回提供したのは、その系譜にまたひとつ傍証を加えたにすぎない。

3,000万ドルは抽象的な数字ではない——これは「大規模モデルの重要訓練が一度で燃やす予算」と同程度の規模だ。つまり本当の変化は、分解できるかどうかではなく、Luが繰り返し強調する2つのシフトにある：参加者が「専用ハードウェアを造れる少数の人々」から「GPUを持つ人全般」に変わり、暗号学のバックグラウンドがない人すら、Devinの力を借りれば因数分解を加速できるようになった。

最後の一撃が最も破壊力を持つ：以前はINRIAのような機関が6か月かけてようやくGNFS（現在、大整数分解において最速のアルゴリズム群）のコードに手を加えられるだけだったが、今では1人のエンジニアが18のDevinセッションを起動し、3週間でCADO-NFS（INRIAのオープンソース実装）をGPU版に改造できる。

自宅のHTTPS証明書について言えば——通常それは2048ビットだ。RSA-2048（約617桁）はRSA-1024より10億倍難しく、GNFSによる今回の効率化ではほぼ届かない。Luもはっきり書いている：「RSA-2048は意味のある影響を受けていない。」

つまり今回のAIが引き裂いたのは「みんなが使っている暗号がすべて終わった」という事態ではなく、「中強度の暗号」を国家級の能力から企業級の能力に引きずり下ろしたことだ——この中間の強度は、実は多くの古いシステム、組み込み機器、10年もの間更新されていない鍵が今も使っている領域だ。

参入障壁は下がったが、RSA-2048はまだ遠い

Luはこの件の真の意味をかなり率直に語っている：暗号解析、計算数学、ひいては大規模な科学計算のほとんどにおいて、参入障壁は以前よりずっと低くなった。これはAIが新しいアルゴリズムを発明したのではなく、専門家の人月を要していた作業を、GPUエンジニアが数週間で片手間でできるものに変えたのだ。

Devinは新しい数論アルゴリズムを提案したわけではない。使った一般数体篩法（GNFS。大整数を2つの因子に分解する古典的アルゴリズム）（現在知られている最も高速な大整数分解の汎用アルゴリズム）は、2020年の研究者たちと同じ工程であり、いわゆる「glas」もINRIAのオープンソースツールCADO-NFSのGPU移植版にすぎない。Devinが真に行ったのは、格子篩（GNFSの中で最も計算資源を消費する工程で、大きな表から候補データを繰り返し篩い分ける）という「表面上は地味だが実際にはメモリ帯域を猛烈に消費する」負荷を、GPUに移植して走らせたことだ。Luの言葉を借りれば、GPUの「特異なメモリシステム」を活用すればいいだけ。

皮肉なことに、この負荷はトレーニングクラスタの余り資源とまさにぴったり噛み合う。LLM訓練に使われるNVL72ラックには18台の相互接続されたマシン（NVIDIA製72基のGPUを相互接続した統合ラック。大規模モデル訓練専用に設計されている）があるが、大規模モデルのタスクは1台のマシンをフル稼働させることは少なく、単一ノードで互いに独立し、いつでも横取りされうる零細な空きを残す。格子篩はまさに「単一ノードで、秒単位で横取り可能で、互いに独立」という仕事だ——この作業はそのような断片の上で空回りするように走り、ほぼゼロの限界コストで処理された。合計で4,900 GPU・日、すなわち13.5 GPU年、約40万ドル。

このマッチング関係を理解できる人なら、Luが投げかけるより大胆な判断に自然に行き着く：問題がプログラミングによって分解可能である限り、自律的なソフトウェアエンジニアリングエージェントに自由に試させる価値がある。ハードルは数学にはなく、コードにある。そしてコードの部分は、AIがすでに人間に代わって歩ける。

今後の看点は、検証可能なシグナルで追える：

・RSA-1024の「$30Mで1回」はまだ机上の見積もりだ。Lu自身の数字であり、第三者による再現検証はない。スーパーコンピュータ企業や先端研究所が公開記録で実際に1024ビットに到達し、コストが本当に3,000万ドル規模に抑えられれば、「超大規模計算資源による暗号解析の代替」というパスが実証されたことになる。

・エージェントがより困難な領域に進出したかどうかが次の分岐点になる。たとえば純粋数論、計算化学、あるいは天体物理学のように、専門家による「どの道筋を選ぶべきか」の判断が必要な研究コード。非暗号学分野で同型の「専門家数人・数週間 vs エージェント・数週間」比較事例が出れば、Devinのモデルは分野を選ばないことが示される。

・フラグメント算力市場が立ち上がるかは、空き資源の扱い方にかかっている。NVL72のようなトポロジ上の空きが、取引可能な「算力在庫」として認識され始めれば、「単一ノード・横取り可能・互いに疎結合」なタスク（より多くのGNFS、分散科学計算、バッチシミュレーションなど）を流し込むプラットフォームが現れ、トレーニングクラスタのTCO（総所有コスト。調達、運用、電気代などを含む）が再計算されるだろう。

・RSA-2048は短期的には動かない。Luははっきり書いている：2048ビットは1024ビットより約10億倍難しく、「現在の仕事が実現可能性に与える影響はほぼない」。いつ「2048ビット突破」のプレプリントや機関声明（単なるブログの推測ではなく）が出れば、それが真の地震だ。

・既存の2048ビットRSA証明書はこの件によって置き換えられたりしない。CA（認証局。ウェブサイトにHTTPS証明書を発行する信頼された第三者機関）とブラウザ側の更新サイクルは数年単位だ。判断が成立するシグナルは、主要CAが自主的に2048ビットルート証明書（ブラウザとOSに組み込まれた最高信頼レベルの証明書）を3072ビットや4096ビットに前倒しで切り替えることであり、世論の中の散発的な議論ではない。

あなたが確認できる、3つの数字

RSA-260自体は専門家だけが取り組める問題で、一般人が再現するのは不可能だ。ただ、以下のいくつかの重要数字と概念はすでに公開されており、誰でも照合できる。

6年、3週間、4日——まず照合すべきはこの3つの時点だ。RSA-250は前回の公開記録で、2020年2月に6名の研究者によって達成された。RSA-260は6年間未解決だったが、今回は主工程を4日で完走し、Devinが着手してから結果が出るまで約3週間だった。6年対3週間、未解決対一発突破——その意味は改めて説明するまでもない。

4,900 GPU・日、約40万ドル、約3,000万ドル——次はコスト曲線の数字だ。原文にはっきり書かれている：GNFS（一般数体篩法）（現在、大整数分解において最速の古典アルゴリズム）でRSA-260を分解するには約4,900 GPU・日、つまり13.5 GPU年、市価換算で約40万ドルかかった。うち多項式選択が643 GPU・日、篩工程が3,813 GPU・日、連立一次方程式の求解が467 GPU・日だ。Cognitionは「以前の公開最適解のおよそ10分の1」とうたっているが、第三者による再現検証は確認されていない——これはベンダー自己申告の数字であり、割り引いて見る必要がある。

309桁、10億倍、影響なし——3つ目は著者自身が引いた境界線だ。原文は2つの明確な線を示している：RSA-1024（約309桁）はGNFSのスケール則で外挿（既知のデータ点から未知の点を推定する手法）すると約3,000万ドルで、トップクラスの機関なら到達可能。RSA-2048は依然としてRSA-1024の約10億倍の難易度で、GNFSルートへの影響は限定的と著者は明言している。つまりブラウザで使われている2048ビット証明書は現時点で影響を受けていない。動いたのはコスト曲線と、それを変えられるのは誰かだ。

もうひとつ注目すべき点がある：このパイプラインのハードウェアは珍しくもなく、NVL72ラック内で大規模モデル訓練の合間に余る断片的な計算資源（NVIDIA製72基のGPUを相互接続した高密度ラック）の上で動いており、「訓練のついでに問題を解いてしまった」に等しい。ハードルはハードウェアにはなく、誰かがそれを書き出すことにあった——そしてこの書き出しをDevinは自動で行い、著者の役割は優先順位の設定、性能チェック、軌道修正だけだった。