2026年9月3日、RSA因数分解課題は新たなマイルストーンを記録しました。260桁（862ビット）の半素数RSA-260が、2つの130桁の素数に因数分解されたのです。この因数分解は、エリック・ルーとコグニションの研究チームによって実施されました。彼らは、一般に100桁以上の整数に対して最も効率的な既知のアルゴリズムである一般数域篩算法（GNFS）の新しいGPU加速実装を使用しました。前の公開記録は2020年2月に設定されたRSA-250（250桁、829ビット）で、国際的な学術共同体によって達成されました。
The image depicts the outcome of factoring RSA-260, highlighting the successful decomposition of the 260-digit semiprime into its prime factors, which aligns with the article's discussion of the milestone.
## この因数分解の達成方法
一般数域篩算法は、3つの主要な連続段階を経て進行されます：多項式選択、格子篩、線形システム解法。多項式選択は、篩の過程で有用な関係を最大化する代数数場を選択します。格子篩は、最大の計算量が必要な段階で、小素数で完全に因数分解される整数（滑らかな数）を、特別なq格子点で多項式を評価することで探します。各作業単位では、大きな数のランダムな位置で大量の読み書きを行い、このメモリアクセスパターンは、歴史的にGPUでの最適化が困難でした。得られた関係は、GF(2)上の巨大な疎行列を形成し、ブロック・ウィーデマン法が線形従属を見つけ、対象数に対する合同余りを導き出します。そこから因子が導かれます。
コグニションの実装は、オープンソースのCADO-NFSスイートを修正してほぼすべての部分を置き換えました。
- GPU適応の第1段階多項式選択（gps1）は、msieveのカーネルを組み込みました - 新しいGPU格子篩（glas）が、CADOのCPU専用lasに代わって導入されました - 巨大な作業単位処理に対応するためのCADOの最適化ヘッド - 並列化された重複排除、消去、統合されたマージ/リプレイプログラム - GPU最適化されたブロック・ウィーデマン線形ソルバー - GPU加速された平方根ステップ - 関連するオーケストレーション・スクリプト
cado-nfs.py自体、第2段階多項式選択（polyselect_ropt）、makefb、dup1は変更されませんでした。
このプロジェクトにはアルゴリズム上のブレークスルーはありません。成果は「良きパフォーマンス・エンジニアリング」から得られました。現代のGPUの高いメモリ帯域幅を活かすためのものです。格子篩が主な技術的課題でした：大規模での効率的な擬似ランダムなメモリアクセス・パターンの処理が必要でした。これは、カーネルの最適化とメモリシステムの調整を多大に必要としました。
## コストと計算能力
この因数分解には、約4,900 GPU-days（13.5 GPU-years）が消費されました。内訳は以下の通りです：
- 多項式選択には643 GPU-days（オペレーターのエラーにより異常なまでに高い数値） - 格子篩には3,813 GPU-days - 線形システム解法には467 GPU-days（7%程度がクラッシュや事前割り当てによる損失）
現在の市場のGPU価格で換算すると、ざっと40万ドルです。重要なのは、この計算が**限界コストなし**で行われたことです。コグニションのLLMトレーニング・クラスターの余剰または断片化した計算能力を利用しました。これらのクラスターはNVL72ラック（各ラックには18台のコンピュータがNVLinkで相互接続されています）を使用し、ジョブ・スケジューラーは高速なインターコネクトを活用するために、ラック内のワークロードを詰め込む必要があります。これにより、1桁%程度のノードがアイドルまたは未活用になります（例えば、17台ではなく18台のノードがアクティブなラック、またはフェイルオーバー用に予約されたノードなど）。チームは、このスケジューラーを「乗り込む」ことで、低優先度で事前割り当て可能な格子篩ジョブをこれらの隙間に埋め込みました。これらのジョブは、並列処理可能で、安全に即時中断でき、GNFSの作業の大部分を占めます。
## RSAキーのサイズへの影響
RSA-1024（309桁の10進数、1024ビット）は、標準的なGNFSのスケーリングに従ってRSA-260より約78倍の計算を要すると推定されています。現在の市場のGPU価格では、ざっと3,000万ドル（1つの数に対して）となります。ウォールクロック・タイムは、より多くのGPUを追加することでコストとトレードオフ可能です。著者によると、現在のこの実装は大幅に最適化されておらず、さらなる作業によりコストを2倍以上削減できるとのことです。
RSA-1024の危険性は新しいものではありません。国家レベルの能力がRSA-1024を経済的に因数分解できるという推測は、2000年代半ばのTWIRLやベルンスタインの行列マシンの提案以来ありました。この作業で変化した点は3つあります：(1) おそらくより低いドルとタイム・コスト、(2) 専門的なハードウェアではなく、市販のGPUで計算可能なより多くの当事者、(3) 非暗号学者でもAI支援のエンジニアリングで因数分解コードを最適化するのがより容易になったことです。
これに対して、RSA-2048（617桁の10進数、2048ビット）は、GNFSの下でRSA-1024より約10億倍困難です。この作業で得られた効率性の向上が、その実現性に与える影響は小さいです。
## コンテキスト：RSA因数分解課題
RSA因数分解課題は、1991年にRSA研究所によって開始されました。整数因数分解の研究を奨励し、RSAキーの安全性を実証するために行われました。この課題は、拡張された2001年の課題からRSA-576とRSA-640が因数分解された後、2007年に終了しました。業界は、この時点で暗号解析の強度についてより高度な理解を得ていました。RSA-260は、この課題の終了後に因数分解されたもので、RSA-100からRSA-500までの各桁数のラベル付けが続いており、現在最大の公開済み解です。
## 開放的な疑問点と限界
この40万ドルという市場コスト推定は、現在のGPU価格と、このプロジェクトで得られた特定の実装を前提としています。あるコメント投稿者は、最新のCPUハードウェア（例えば96コアのAMD EPYC）が、2017年のSkylake Xeonベースラインからの整数パフォーマンスを大幅に改善しており、CPU-GPUのコストギャップが狭まっていると指摘しています。この因数分解はまた、大規模なGPUクラスターの余剰容量に依存しており、ほとんどの活動家には利用できません。ボットネットや盗まれたクラウド認証情報を持つ敵対者は、格子篩段階を異なる方法でコスト分配できますが、線形代数学習段階では、高帯域幅のインターコネクト（Infiniband/NVLink）が必要で、ヘテロジェネアスな、または非信頼できるインフラ上で再現するのは困難です。
GNFSのアルゴリズム上の改善は見られませんでした。この作業は、測定、最適化、エンドツーエンドのパイプラインの実行を反復する能力を持つ自律エージェントによって、より低い参入障壁で大規模な計算数学および科学計算研究が可能であることを示しました。著者、つまり数論に関する専門知識を持たない人は、デビンを高レベルの部分で指示しました：優先順位の設定、基準の確立、作業が軌道から外れた時の認識です。エージェントは、測定、最適化、エンドツーエンドのパイプラインの実行を、平均3セッション、最大18セッションで3週間実行しました。
この結果は、AI支援のツールでエンジニアリング・サイクルを自動化することが十分なGPU計算能力があれば、大規模な計算数学および科学計算研究への参入障壁を大幅に低減できることを強調しています。