155桁の数をグラフィックスカードで分解
大きな数を素因数に分けるのは難しい。そしてその難しさは暗号にとって重要だ。だからこそ論文は、この結果が何を脅かさないのかをていねいに述べている。公開された「RSAチャレンジ」の数は、素因数分解の手法を測るベンチマークとして使われている。RSA-155はその一つで、155桁、つまり512ビットだ。
二つのふるい、それぞれの記録
主要なアルゴリズムは二つの系統に分かれる。数体ふるい法は、とても大きな数での王者だ。1999年にRSA-155を分解し、論文によれば、一般の記録は2026年の270桁の数RSA-896だという。より古い二次ふるい法は漸近的に遅く、著者ら自身の言葉では、一般の記録には「場違いな道具」だ。ただし、こちらにも独自の記録表がある。二次ふるい法で分解された最大の数は、2025年6月のRSA-150で、1万1664 CPUコア時間を使った。
二次ふるい法は、小さな素数の集合だけで完全に素因数分解できる小さな数をたくさん探し、そのあと線形代数でそれらを組み合わせて、Nを法として等しい二つの平方数x²とy²をつくる。最後に最大公約数をとると、因数が一つ見つかる。コンピューターの上では、これはグラフィックスプロセッサー(GPU)にとって悪夢だ。メモリへのアクセスはどんなキャッシュにも収まらないほど散らばり、判定は分岐だらけで、最後の代数計算は、どのメーカーのライブラリも対応していない二進の算術で行われる。これまでのGPUでの試みが高速化できたのは、個々のステップだけだった。
すべてをグラフィックスカードの上で
ドイツのパーダーボルン大学数学研究所のファビアン・ヤヌシェフスキ(Fabian Januszewski)とクリストフ・ハインリヒス(Christoph Heinrichs)は、オープンソースの二次ふるい法CUDA-MPQSをつくった。多項式の準備、ふるい、候補の確認、部分的な結果の照合、行列の構築、その求解、最後の平方根まで、すべての段階がGPU上で動く。ふつうのプロセッサーは、全体の指揮、準備、入出力を担うだけだ。著者らは、ホスト側に残ったわずかなステップを明示している。100桁でのテストでは、ふるいの時間の99.9%でGPUが稼働しており、プロセッサーを待って止まることはなかった。
規模を大きくすると、微妙なバグが表に出た。RSA-155の大きさでは、ふるいの途中で使う8ビットのカウンターが、まさに最も価値のある候補であふれ、その98〜99.5%を黙って捨てていた。チームはこれを飽和型のカウンターに置き換え、同じ結果を与えることを証明した。
約1日でRSA-155
2026年7月14日、このパイプラインはRSA-155を78桁の素数二つに分解し、GPUとホストの両方で確認した。
- ふるい:16ノードにまたがる64枚のNVIDIA H100 GPUで10.8時間。約1730万の関係式を集めた。
- 線形代数:1枚のH100で10.9時間。行数1670万、非ゼロ要素6億8400万の行列を扱った。
- 合計:700.6 GPU時間と242キロワット時。開始から因数が得られるまで約24時間。コストの98.4%はふるいだった。
著者らの知るかぎり、これは二次ふるい法で分解された最大の整数で、これまでの記録を5桁上回る。しかも、この方法の最も単純な変種で達成された。最近の記録は関係式ごとに三つの「大きな素数」を使っていたが、この変種は一つしか残さない。
最高のプロセッサーより速い
100桁の数なら、H100 1枚で29.2秒、一般向けのRTX 5070 Tiで51秒で終わる。同じ数で双方のエネルギーを測りながら行った管理された比較では、H100 1枚は、AMD EPYCプロセッサーの96コアで動く最速のCPU版二次ふるい法より3.6〜4.2倍速く、別の標準的なパッケージより約9〜10倍速かった。チームはRSA-150も302.9 GPU時間で分解し直した。前回の記録は1万1664コア時間だったが、著者らは、この比は同じ条件での速度向上ではないと強調している。
暗号への脅威はない
著者らははっきりと述べている。RSA-155はすでに分解されていたこと、これは一般の素因数分解の記録ではないこと、そして「ここには安全性の余裕を狭めるものは何もない」こと。コードは設計上、約155桁までに制限されてもいる。彼らの関心は別のところにある。不規則で分岐だらけのアルゴリズムでも、丸ごとGPUの上で動かせると示すことだ。次の自然な標的として彼らが挙げるのは、数体ふるい法の中心にあるGPUの格子ふるいだ。著者らによれば、その仕事はその後すでにほかの人たちが始めており、既存のパッケージをGPUに移植したものでRSA-260とRSA-896が分解された。後者はClaudeを使って行われた。
利益相反。 著者らは、生成AIとエージェント型のコーディングツールを使ったと述べている。ソフトウェア開発には、AnthropicのClaudeモデル(Claude Code経由)とともに、OpenAIのGPTとGoogleのGeminiのモデルを、データと原稿の準備にはClaudeモデルを使った。AIの出力はすべて人の手で見直し、検証したという。この記事もClaudeが書いた。