RSA-260が35年ぶりに素因数分解されたので計算方法を調べた

Cognitionのエンジニア Eric Lu（@penlume）は2026年9月3日、130桁の整数と「divides RSA-260」の一言だけをXに投稿した。
RSA-260は1991年のRSA素因数分解チャレンジで出題された260桁（862ビット）の合成数で、35年間だれにも分解されていなかった。
投稿の数分後にはWikipediaのRSA numbersの項が更新され、2020年のRSA-250（829ビット）を抜いて、汎用アルゴリズムで分解された最大の数になった。

投稿された数で手元のM4 Mac miniのPythonからRSA-260を割ってみると、余りは0で、もう片方も130桁になった。
どちらもsympyの素数判定を通った。

N = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199
p = 4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581
q = N // p
print(N % p == 0, len(str(q)), N.bit_length())   # True 130 862
import sympy
print(sympy.isprime(p), sympy.isprime(q))        # True True

q = 5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379。
pもqも431ビットで、出題どおり素数2つの積だった。

1991年のRSA素因数分解チャレンジ

RSA素因数分解チャレンジは、RSA暗号の安全性が「大きな数の素因数分解は難しい」という前提に立っていることから、RSA Laboratoriesが1991年3月18日に始めた公開の懸賞問題だ。
最初のシリーズはRSA-100からRSA-617まで10進の桁数で名前が付いていて、RSA-260もこのシリーズにある。
2001年に追加されたRSA-576からRSA-2048はビット数で名前が付き、こちらには1万ドルから20万ドルの賞金が設定されていた。

チャレンジ自体は2007年に終了している。
RSA-260には終了時点で賞金が設定されていなくて、今回の分解にも賞金は出ない。
10進シリーズのRSA-270以降と、ビットシリーズのRSA-896、RSA-1024、RSA-1536、RSA-2048が未分解で残っている。

これまでの記録

計算量の単位のコア年は、CPUコア1個を1年間回した分の計算量を指す。

数	ビット	分解した年	計算量
RSA-155	512	1999年8月	国際チーム（Alec Muffettらが参加）
RSA-768	768	2009年12月	2.2GHzのOpteron1コアで約2000年分、2年がかり
RSA-240	795	2019年11月	2.1GHz Xeon Gold 6130で約900コア年
RSA-250	829	2020年2月	同じCPUで約2700コア年
RSA-260	862	2026年9月	未公表

RSA-240とRSA-250はどちらもBoudot、Gaudry、Guillevic、Heninger、Thomé、Zimmermannの6人のチームで、フランスのINRIAなどが開発しているオープンソースのCADO-NFSを使った。
RSA-240はRSA-768より大きいのに計算量が半分以下になっている。
発表文では、RSA-768からの高速化をアルゴリズムで3〜4倍、ハードウェアで1.25〜1.67倍と見積もっている。
論文の方でも、アルゴリズムの改良とパラメータの選び方で過去の記録からの外挿より大幅に安くなったと書いている。

投稿から2時間ほどで、1999年にRSA-155を分解したチームにいたAlec Muffettが「Hello from RSA-155, and congratulations!」と返信した。
Cognition創業時メンバーのSilas Albertiは、Wikipediaが編集される前にAIに聞くと混乱していたと投稿している。

どうやって計算したのか

本人は9月4日時点で、アルゴリズム、ソフトウェア、ハードウェア、計算時間のどれも公表していない。
投稿は素因数だけで、Hacker Newsでも手法、ソフトウェア、コア数、所要時間を聞くコメントが付いたままだ。

「7ヶ月かけてランダムな素数を手で試した」という説明が広まっているが、元は同僚のSean（@_seanyneutron）が「EricはCognitionに入った7ヶ月前からランダムな素数を手で試し続けていた。努力は才能に勝る」と書いたジョークだ。
少なくともまとめアカウントのAGTPの投稿では、これが事実として書かれている。
130桁の素数はおよそ3.3×10^127個あるので、1個ずつ試しても当たらない。

手法は公表されていないが、小さい素因数を持たない一般の合成数に対しては、公知の古典アルゴリズムでは一般数体篩（GNFS）が最良とされている。
楕円曲線法やPollardのρ法は小さい素因数を見つける手法で、431ビット同士の積には効かない。
量子コンピュータのShorのアルゴリズムも、この規模を動かせる機械はない。
LedgerのCTO Charles Guillemetも「量子コンピュータは関わっていない」と書いている。

一般数体篩の流れ

一般数体篩は、 $x^2 \equiv y^2 \pmod N$ となる $x, y$ を作って $\gcd(x - y, N)$ から因数を取り出す。
そのために、有理数側と代数体側の値がどちらも小さい素数の積に分解できる組（関係式）を大量に集め、指数の偶奇がそろう組を掛け合わせて平方の合同式を作る。

flowchart TD
    A[多項式選択<br/>Nに合う多項式を探す] --> B[篩<br/>関係式を集める]
    B --> C[フィルタリング<br/>重複と孤立を除く]
    C --> D[線形代数<br/>mod 2で従属関係を解く]
    D --> E[平方根<br/>gcdで因数を取り出す]

最初の多項式選択で、Nを法として共通の根を持つ多項式の組のうち、あとの篩で小さい素数に分解しやすい値を出すものを探す。
ここで選んだ多項式の良し悪しで篩の所要時間が変わる。
篩は、その関係式を数十億件集める段階で、区間を分けて別々の機械に配れる。
RSA-250のときの計算量の内訳は、発表メールによると篩が2450コア年、行列が250コア年。
計算にはGrid’5000、EXPLOR、Juelich、UCSDの計算資源が使われた。
フィルタリングで重複した関係式と、全体で1回しか現れない素イデアルを含む関係式を捨てて行列を小さくする。
RSA-250では、そのあとの線形代数で約4億500万行の疎行列にブロックWiedemann法を回した。
行列を複数ノードに分けると行列ベクトル積にノード間通信が生じて、RSA-240ではOmni-Path接続の8ノードで、積1回あたりの約3割が通信だった。

規模の見積もり

実際の計算量は分からないが、桁の目安なら式で出せる。
一般数体篩の計算量は $L_N[1/3, (64/9)^{1/3}]$ で表される。
$\exp\left(c (\ln N)^{1/3} (\ln \ln N)^{2/3}\right)$ の形で、ビット数に対して指数関数よりは緩いが多項式よりはずっと速く増える。
この式に829ビットと862ビットを入れて比を取ると約2.6倍。
RSA-250の2700コア年に掛けると7000コア年前後になるが、式には低次の項が省かれているし、RSA-240のようにパラメータで実測は大きく変わる。

コア年を単純に割ると、7000コア年は1万コアに配れれば月単位になる。
ただし線形代数の段階は大容量メモリとノード間通信がいるので、この割り算だけでは実際の構成も期間も決まらない。

CADO-NFSは2020年以降も開発が続いている。
Eric LuがCADO-NFSをそのまま使ったのか、自前の実装なのか、どれだけの機械を使ったのかは、本人の発表を待つしかない。

RSA-1024とRSA-2048の場合

同じ式で862ビットからRSA-2048までの比を取ると約9×10^10倍、RSA-1024でも約78倍になる。
2048ビットは今回の計算を1000億回分繰り返す規模になる。
RSA-250の2700コア年を829ビットから1024ビットへ同じ式で外挿すると、200倍の約54万コア年になる。
RSA-1024は今も未分解で、NIST SP 800-57はRSA-1024を80ビット相当以下と見積もり、新たな暗号保護には使わないとしている。

汎用の数は力技しかないと思っている。