Loading article…
整数因数分解とは、与えられた正の整数を割り切る素数を特定するプロセスです。これを迅速に行うことは、暗号学において応用されています。その難易度は、数の大きさや形式、そして素因数によって異なります。現状では、大きな半素数（そして実際には、小さな因数を持たないほとんどの数）を因数分解することは非常に困難です。
最初の大規模な分散型素因数分解はRSA-129でした。これは1977年のサイエンティフィック・アメリカン誌の記事で紹介された129桁のチャレンジ番号で、RSA暗号システムを初めて普及させたものです。1993年9月から1994年4月にかけて、MPQSを用いて素因数分解が行われました。約600人がインターネットを通じて関係式を提供し、計算の最終段階はベル研究所のMasParスーパーコンピュータで実行されました。
1999年1月から8月にかけて、RSA社が作成した155桁のチャレンジ番号であるRSA-155は、 GNFSを用いて素因数分解され、その際も大規模なグループから提供された関係式が用いられました。計算の最終段階は、 SARAアムステルダム学術コンピュータセンターのCray C916スーパーコンピュータ上でわずか9日強で完了しました。
2002年1月、ボン大学の約25台のPCを用いて数ヶ月かけて2953 + 1の158桁の余因子の因数分解が発表された。最終段階は6台のPentium-III PCのクラスターを使用して行われた。
2003年4月、同じチームがBSIの約100個のCPUを使用して160桁のRSA-160暗号を素因数分解し、計算の最終段階はSGI Originスーパーコンピュータの25個のプロセッサを使用して行われた。
576ビット（174桁）のRSA-576は、2003年12月にNFSNETコラボレーションのメンバーによって、BSIとボン大学のリソースを使用して素因数分解されました。その後まもなく、あるグループが2¹⁸²⁶ + 1の164桁の余因子を素因数分解したことが発表されました 。
2005年2月から5月にかけて、日本のNTTと立教大学のコンピュータを使用して、11 281 + 1の 176 桁の余因子が素因数分解されました。 [ 1 ]
663ビット（200桁）のRSA-200チャレンジ番号は、2003年12月から2005年5月にかけて、ドイツのBSIにある80個のOpteronプロセッサのクラスタを使用して素因数分解されました。発表は2005年5月9日に行われました。[ 2 ]その後、2005年11月に、わずかに小さいRSA-640チャレンジ番号の素因数分解が行われました。
2009年12月12日、 CWI、EPFL、INRIA 、NTTの研究者を含むチームが、以前の記録の著者らに加えて、232桁の半素数であるRSA-768を素因数分解した。 [ 3 ]彼らは、シングルコア2.2GHzのAMD Opteronで約2000年分の計算量を 使用した。
12 151 − 1（542ビット（163桁））は、1993年4月から7月にかけてCWIとオレゴン州立大学のチームによって素因数分解された。[ 7 ]
2 773 + 1 は、774 ビット (233 桁) で、2000 年 4 月から 11 月の間に「ザ・カバル」によって素因数分解され、行列ステップは RSA-155 にも使用された Cray で 250 時間かけて実行されました。[ 8 ]
2 809 − 1 は 809 ビット (244 桁) であり、その因数分解は 2003 年 1 月初めに発表された。篩分けは CWI、科学計算研究所、ボン大学の純粋数学部門、および民間のリソースを使用して行われた。線形代数のステップはアムステルダムの SARA で行われた。[ 9 ]
6 353 − 1 (911 ビット (275 桁)) は、SNFSを使用して 2005 年 9 月～2006 年 1 月の間に素因数分解されました。[ 10 ]
2 1039 − 1、1039 ビット (313 桁) (ただし、23 ビットの因数は既に知られていた) は、2006 年 9 月～2007 年 5 月の間にNTT、EPFL、ボン大学のグループによって因数分解された。[ 11 ] [ 12 ]
2 1061 − 1、1061 ビット (320 桁) は、2011 年初頭から 2012 年 8 月 4 日にかけて、CSU Fullerton のグループによって、nfs@home BOINCプロジェクトを使用して約 300 CPU 年分のふるい分けを行い、因数分解されました。線形代数は SDSC の Trestles クラスターと TACC の Lonestar クラスターで実行され、さらに 35 CPU 年が必要でした。[ 13 ]
1000 から 1200 の間のnを持つ数 2 n − 1の因数分解されていない部分はすべて、2010 年以降、複数の数に対してふるい分けステップの大部分を同時に実行できる多数ふるい分けアプローチによって因数分解されました。 [ 14 ]正確には、n = 1081 (326 桁) は 2013 年 3 月 11 日に完了しました。n = 1111 (335 桁)は2013 年 6 月 13 日に完了しました。n = 1129 (340 桁) は 2013 年 9 月 20 日に完了しました。n = 1153 (348 桁)は2013 年 10 月 28 日に完了しました。n = 1159 (349 桁)は2014 年 2 月 9 日に完了しました。 2014年5月29日時点でn = 1177（355桁）、2014年8月22日時点でn = 1193（360桁）、2014年12月11日時点でn = 1199（361桁）に達しました。最初の詳細な発表は2014年8月下旬に行われました。このプロジェクトの総作業量は2.2GHz Opteronで約7500CPU年であり、そのうち約5700年が篩分け処理に、1800年が線形代数処理に費やされました。
究極の素因数以外の素因数の記録は155桁の10進数で、12 311 −1の素因数です。[ 15 ] [ 16 ] [ 17 ]
2007年末の時点で、メモリ価格の継続的な下落、マルチコア64ビットコンピュータの容易な入手、ggnfs [ 18 ]を介した効率的な篩分けコードと仕上げ段階用のmsieve [ 19 ]などの堅牢なオープンソースソフトウェアの入手により、特別な数学的経験を持たない1人が数台のPCで数か月以内に最大750ビット（226桁）の特殊形式数と最大約520ビット（157桁）の一般形式数を素因数分解できるようになりました。[ 20 ]篩分けのために数十台のPCの協力を確保できれば 、これらの上限は約950ビット（286桁）[ 21 ]と600ビット（181桁）[ 22 ]に増加します。現在、仕上げ段階用の単一マシンのメモリ量とCPUパワーは、進歩に対する同等の障壁となっています。
2009年、512ビット（155桁）のRSA鍵が解読された。この鍵は、インターネット上で見つけたソフトウェアを使ってTI-83グラフ電卓に署名するために使用されており、これが最終的にテキサス・インスツルメンツの署名鍵をめぐる論争へと発展した。
2013 年 9 月には、機関のリソースを使用して 696 ビット (210 桁) のRSA-210 が素因数分解されました[ 23 ]。2013 年 3 月から 2014 年 10 月の間には、別の 210 桁の数 ( 49 から始まるホーム素数列の 117 番目の項) [ 24 ]が、ふるい分けのために Amazon EC2 マシン[ 25 ]で 7600 ドル相当の処理時間を使用し、線形代数のためにデュアル Xeon E5-2687W v1 で 4 か月使用して素因数分解されまし た。
ショアのアルゴリズムによって他の量子的方法ではなく確実に素因数分解された最大の数は、2012年に素因数分解された21である。 [ 26 ] [ 27 ] 15は以前にいくつかの研究室によって素因数分解されており、その後35を素因数分解しようとする試みは失敗に終わった。[ 27 ]
量子コンピュータで特定の数を因数分解するために他の方法が使用されています。2012 年 4 月、室温 (300 K) の NMR断熱量子コンピュータ による 143 = 13 × 11 の因数分解がグループによって報告されました。[ 28 ] 2014 年 11 月、 2012 年の実験では実際にはもっと大きな数も知らずに因数分解していたことが発見されました。 [ 29 ] [ 30 ] 2016 年 4 月、18 ビットの数 200,099 がD-Wave 2X量子プロセッサ上の量子アニーリングを使用して因数分解されました。[ 31 ]その後まもなく、291,311 という数が室温よりも高い温度の NMR を使用して因数分解されました。[ 32 ] 2019年後半、Zapata computingは1,099,551,473,989の素因数分解に成功したと主張し、[ 33 ] 2021年にこの計算を記述した論文を発表した。[ 34 ] 2024年には、量子アニーラーに素因数分解問題を組み込む新しいアプローチが提案され、(i) 21×12の素因数分解問題をD-Wave Pegasusアーキテクチャに組み込み、(ii) ハイブリッド技術を利用せずに量子アニーラーを使用して8,219,999の素因数分解を実現した。[ 35 ]
そのため、量子コンピュータによる因数分解の主張は、必要な量子ビット数を減らすために古典的計算に大きく依存しているとして批判されてきた。[ 36 ] [ 37 ] 例えば、1,099,551,473,989 の因数分解は、問題を 3 量子ビットの量子回路に縮小するために古典的な前処理に依存していた。[ 34 ]さらに、この論文で因数分解された 3 つの数 (200,099、291,311、および 1,099,551,473,989) は、それぞれループの反復が 3 回、1 回、および 1 回しか必要なく、フェルマーの因数分解法を使用して簡単に因数分解できる。2025 年に、量子コンピュータを使用した既存の因数分解記録がVIC-20を使用して複製され、特定の構造を持つ数の因数分解の容易さが強調された。[ 27 ]
{{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク){{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)