RSA 260の素因数分解

過去数週間にわたり、Cognitionの研究チームと私は、分散コンピューティングをより有効活用するためにジョブスケジューラを最適化してきました。概念実証として、そして過去10年ほど趣味で素因数分解を楽しんできたこともあり、私はDevinを活用してRSA-260の素因数分解を達成しました。この目的のために、私のDevinは世界最高性能のGPUラティスシーバーを構築し、これにより公表されている既存の最先端技術よりも10倍低コストで数を素因数分解できるようになりました。以下にその素因数分解を示します: 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199 = 4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581 × 5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379 RSA-260（260桁の数）は、RSA暗号システムの解読の実現可能性をベンチマークする、RSA Factoring Challengeにおける最大の公開解決済み問題の新しい記録を樹立しました。以前の記録であるRSA-250は2020年2月に樹立されました。参考までに、最先端のRSA公開鍵は2048ビット（約617桁）の素因数分解問題を抱えていますが、1024ビット（約309桁）のRSAは2013年に非推奨となりました。 以下に、これがどのように達成されたかの詳細を説明しますが、2つの重要なポイントがあります: ハイパースケーラーまたはフロンティアAIラボは、おそらく1件あたり約3000万ドルのコストでRSA-1024を素因数分解できるでしょう。さらに、もう少し最適化すれば、おそらく大幅に少なくなるでしょう。一方、RSA-2048はRSA-1024よりも約10億倍困難であり、この作業によって有意義に影響を受けるようには見えません。 Devinは、計算数論とGPUパフォーマンスエンジニアリングの交差点にある困難な問題を解決するのに十分強力なソフトウェアエンジニアです。私の役割は主に、優先順位を設定し、ベンチマークを確立し、作業が軌道から外れたときに認識することでした。Devinはそれ以外は、測定、クラスター運用、およびエンドツーエンドの最適化を自律的に処理しました。これは、高度に専門化されたドメインエキスパートのチームによる数ヶ月にわたる作業に取って代わるものでした。 結論として、暗号解読作業、より広範な計算数学、そしておそらくほとんどの大規模科学計算研究の参入障壁は、以前よりもはるかに低くなっています。プログラミングが研究問題を解決するために使用できる場所ならどこでもエキサイティングな仕事が待っています。自律型ソフトウェアエンジニアリングエージェントがこれらの分野に応用されたときに何ができるか、野心的になって探求することを皆さんに奨励します！ どうやってこれが起こったのか？ #一部で流れている主張とは異なり、私は130桁の素数を手作業で推測してRSA-260を素因数分解したわけではありません。Cognitionはまだ数千量子ビットの量子コンピュータを構築していません。RSA-260は、Devinを使用して準備および実行された、GPU用の汎用数体篩法（GNFS）の新しい実装によって素因数分解されました。GNFSは、約100桁を超えるほとんどの数に対して既知で最も効率的なアルゴリズムであり、以前の記録的なRSA数分解でも使用されていました。 この実装は、大幅に改変されたCADO-NFSでした。アルゴリズム的な進歩はほとんど報告していません。GPU上でのラティスシービングとスパース線形システムソルバーの実装には、GPUの途方もないメモリシステムを活用するための「昔ながらのパフォーマンスエンジニアリング」しか必要としませんでした。 コスト見積もり# 合計で、この素因数分解には約4,900 GPU日、つまり13.5 GPU年かかったと推定しており、現在の市場価格で約40万ドルです。詳細には、最新のGNFS実装はいくつかの段階で逐次実行されます。多項式選択、ラティスシービング、線形システムソルバーです。時間の内訳は以下の通りです。 643 GPU日（多項式選択、これはオペレーターの不手際により異常に高い） 3,813 GPU日（シービング） 467 GPU日（線形システムソルバー、うち約7%はクラッシュやより重要な作業によるプリエンプションのため進捗しませんでした） 私は、クラスターの数パーセントを使用して、ジョブスケジューラを最適化して分散コンピューティングの使用を改善する過程で、サイドプロジェクトとしてこれを行いました。より大きなRSAインスタンスにとってこれは何を意味するのか？ RSA-1024は309桁に相当します。標準的なGNFSのスケーリングによると、これはRSA-260よりもわずか78倍の計算量です。市場のGPU価格でRSA-1024を素因数分解するコストは、約3000万ドルと推定しており、これは壁時計時間とトレードオフできます。現在の実装が大幅に最適化されていないことは事実です。さらに適度な作業でRSA-1024のコストをさらに数倍削減できるとしても、私は驚かないでしょう。 もちろん、RSA-1024が安全でないという事実は新しいことではありません。NSAは2000年代半ばにはRSA-1024を経済的に実行する能力を持っていたのではないかという憶測がありました（例えば、TWIRLやBernsteinマトリックスマシンを参照）。代わりに、以下で説明するように、主な進展は（1）素因数分解のコスト（ドルと時間）が低下する可能性、（2）素因数分解を実行できる当事者が増える可能性（特殊なハードウェアを作るのではなく、十分なGPUがあればよい）、（3）暗号専門家でない人が素因数分解の高速化に取り組むことが容易になったことです。 最後に、効率の向上は、GNFSによるRSA-2048サイズの数の素因数分解の実現可能性にはほとんど影響しないことを強調します。 余剰コンピューティングでの素因数分解# この素因数分解は、他の目的で使用できなかった余剰または断片化されたコンピューティングリソースで、追加コストなしで実行されました。なぜこのコンピューティングが存在するのか？ LLMのトレーニングと推論に使用するクラスターにはNVL72ラックが含まれており、各ラックは名目上18台のコンピュータで構成され、高速なNVLinkで相互接続されています。LLMワークロードは、この高速な相互接続を活用するために、ラック内のコンピュータグループを使用します。ジョブスケジューラは、ラックにワークロードをパックするために制約付き最適化問題を解決する必要があります。このグローバルな割り当てにおいて、一部のラックにはアイドル状態のノードが1つか2つ残ることがあります。時にはジョブがフェイルオーバーに対応するために余剰ノードを要求したり、ラックに17台しかない場合に偶数台のコンピュータを必要とするジョブもあります。私たちにとって、これらの非効率性は全体的なコンピューティングの数パーセントに相当します。 この余剰コンピューティングを活用するために、最初のステップとして、ジョブスケジューラを、最下位の優先度で他のワークロードの周りにシングルノードジョブを埋め込むように調整しました。しかし、容易にプリエンプト可能な一貫したシングルノードワークロードのソースも不足していました。当然、この時点でラティスシービングのことを考えました。これはこの状況に最適です。 ラティスシービングは、数十億の小さな作業単位にわたって非常に並列化可能であり、一度にシングルノードを使用して進捗でき、即座にプリエンプトしても安全です。また、GNFSの計算コストが最も高い部分でもあるため、シービングを完了させることが素因数分解に向けた大きな進歩となります。しかし、これまでのすべての公開GNFS素因数分解記録は、ラティスシービングにCPUのみを使用していました。実際、GPU上でのラティスシービングの効果的な実装の課題のため、GPUラティスシービングが全体としてよりコスト効率が高くなるかどうかは、長い間不明でした。 要するに、私が欠けていたのは、RSA-260を素因数分解するために必要なパラメータを受け入れられる、十分に高性能なGPUラティスシーバーでした。そこで、私は何をしましたか？Devinに尋ねました。 Devinを使用したGNFSの最適化# 太平洋時間の8月13日午前0時11分58秒に、私はDevinにCADO-NFSのCPUラティスシーバーであるlasのドロップイン交換を生成するように指示しました。使用したプロンプトは次のとおりです。 CADO-NFSはGNFSを実行するためのFOSSソフトウェアです。高速なGPUラティスシーバーを開発したいです。これは、CPUラティスシービングの最適化が多くの条件分岐と複雑なメモリアクセスパターンを使用し、GPUカーネルライティングの専門家と数論の専門家の交差が非常に小さいため、現在の技術では歴史的に困難でした。しかし、GPUの総メモリ帯域幅の高さは