離散対数レコード

離散対数記録は、離散対数問題を解く上でこれまでに達成された最良の結果である。離散対数問題は、有限巡回群Gの元gとhが与えられたときに方程式の解x を見つける問題である。この問題の難しさは、ディフィー・ヘルマン鍵共有、エルガマル暗号化、エルガマル署名方式、デジタル署名アルゴリズム、およびこれらの楕円曲線暗号化類似体を含むいくつかの暗号化システムのセキュリティの基礎となっている。これらのアルゴリズムで使用されるGの一般的な選択肢には、 p を法とする整数の乗法群、有限体の乗法群、および有限体上の楕円曲線上の点の群がある。^{[出典が必要]}${\displaystyle g^{x}=h}$

2019 年 12 月に樹立された、素数を法とする整数の現在の^{[更新が必要]}記録は、240 桁の素数を法とする離散対数計算です。特性2 の場合、有限体の現在の記録は 上の離散対数であり、2019 年 7 月に樹立されました。素数指数に制限すると^{[明確化が必要]}、2014 年 10 月に樹立された現在の記録は を超えています。特性 3 の場合、2016 年 7 月に樹立された現在の記録は を超えています。 「中程度の」^{[明確化が必要]}特性のクンマー拡大体の場合、2013 年 1 月に樹立された現在の記録は を超えています。「中程度の」特性の体 (必ずしもクンマー拡大とは限らない) の場合、2022 年に公開された現在の記録は を超えています。^{[出典が必要]}${\displaystyle \mathrm {GF} (2^{30750})}$${\displaystyle \mathrm {GF} (2^{1279})}$${\displaystyle \mathrm {GF} (3^{6*509})}$${\displaystyle \mathrm {GF} (33341353^{57})}$${\displaystyle \mathrm {GF} (2111023^{50})}$

pを法とする整数

• 2019年12月2日、Fabrice Boudot、Pierrick Gaudry、Aurore Guillevic、Nadia Heninger、Emmanuel Thomé、Paul Zimmermannは、 240桁（795ビット）の素数RSA-240 + 49204（RSA-240を超える最初の安全な素数）を法とする離散対数の計算を発表しました。この計算は、数体ふるいアルゴリズムとオープンソースのCADO-NFSソフトウェアを使用して、RSA-240の因数分解と同時に実行されました。計算の離散対数部分は、Intel Xeon Gold 6130 CPU（2.1GHz）を基準として使用して約3100コア年を要しました。研究者らは、アルゴリズムとソフトウェアの改善により、ハードウェアの改善を考慮に入れた後、この計算は以前の記録から予想されるよりも3倍高速になったと推定しています。^{[1] [2]}

p を法とする整数のこれまでの記録は次のとおりです。

• 2016年6月16日、Thorsten Kleinjung、Claus Diem、Arjen K. Lenstra、Christine Priplata、Colin Stahlkeは、数体ふるいを使用して、232桁（768ビット）の安全素数を法とする離散対数の計算を発表しました。計算は2015年2月に開始され、2.2GHzのIntel Xeon E5-2660にスケールアップして約6600コア年を要しました。^[3]
• 2005年6月18日、アントワーヌ・ジューとレイナルド・レルシエは、1.15GHz 16プロセッサHP AlphaServer GS1280コンピュータと数体ふるいアルゴリズムを使用して、 130桁（431ビット）の強素数を法とする離散対数を3週間で計算したと発表しました。^[4]
• 2007年2月5日、トルステン・クラインユングが、再び数体ふるいを用いて、160桁（530ビット）の安全素数を法とする離散対数の計算を発表し、この発表はこれに取って代わられた。計算のほとんどは、さまざまなPCと並列計算クラスターの空き時間を利用して行われた。^[5]
• 2014年6月11日、シリル・ブーヴィエ、ピエリック・ゴードリー、ローラン・アンベール、ハムザ・ジェリェリ、エマニュエル・トメは、数体ふるいアルゴリズムを使用して180桁（596ビット）の安全な素数を法とする離散対数の計算を発表しました。^[6]

また、2016 年 7 月には、ジョシュア・フリード、ピエリック・ゴードリー、ナディア・ヘニンガー、エマニュエル・トーメが 1024 ビット素数の離散対数計算を発表しました。^{[7]彼らは、比較的小さな}サブグループ(160 ビット)に特殊なアルゴリズムを使用して、特殊数体ふるいにかけられる素数を生成しました。これは小さなサブグループですが、1024 ビットのデジタル署名アルゴリズム (DSA) で使用される標準化されたサブグループ サイズでした。

^{[アップデート]}特性数2の有限体における現在の記録（2019年7月現在）は、2019年7月10日にロバート・グレンジャー、トルステン・クラインユング、アルジェン・レンストラ、ベンジャミン・ウェソロフスキー、イェンス・ツムブレゲルによって発表されました。 ^{[8]このチームは、Intel Xeonアーキテクチャに基づくクラスターで25,481,219コア時間を使用して、GF(2 30750} )の離散対数を計算することができました。この計算は、準多項式アルゴリズムの消去ステップを使用した最初の大規模な例でした。^[9]

標数 2 の有限体におけるこれまでの記録は、以下によって発表されました。

• ロバート・グレンジャー、トルステン・クラインユング、イェンス・ツムブレゲルは2014年1月31日に、GF(2 ⁹²³⁴ )の離散対数を約40万コア時間で計算することに成功した。この計算の新機能には、2次元の対数を求めるための改良法と、体​​系的に最適化された降下戦略が含まれる。^[10]
• 2013年5月21日、アントワーヌ・ジューが発表した。彼のチームは、26168 ⁼ ( ²²⁵⁷ ) ^{24要素の離散対数を550CPU時間未満で計算することができた。この計算は、 24080}要素の計算で最近行われたものと同じ指数計算アルゴリズムを使用して行われた。^[11]
• ^{Robert Granger、Faruk Göloğlu、Gary McGuire、Jens Zumbrägel (2013 年 4 月 11 日)。新しい計算は26120}要素のフィールドを対象とし、749.5 コア時間を要しました。
• 2013年3月22日、アントワーヌ・ジュー。これは、21778個の要素を持つフィールドでの以前の計算と同じアルゴリズム[12]を小さな特性フィールドに対して使用しました^。新しい^{計算は、 216個の}要素を持つフィールドの255次拡張として表される²⁴⁰⁸⁰個の要素を持つフィールドに関するものでした。計算には14100コア時間未満しかかかりませんでした。^[13]
• ロバート・グレンジャー、ファルク・ゴログル、ゲイリー・マクガイア、イェンス・ズムブレゲルらは2013年2月19日に、中規模基底体関数体ふるいの新しい変種を2元体に対して使用し、2 ¹⁹⁷¹個の元を持つ体における離散対数を計算した。中規模基底体を使用するために、彼らはその体を2 ²⁷個の元を持つ体の73次拡張として表現した。計算には、Intel (Westmere) Xeon E5650 ヘキサコアプロセッサを搭載したSGI Altix ICE 8200EXクラスタで3132コア時間を要した。^[14]
• 2013年2月11日にアントワーヌ・ジューが発表した。この研究では、小さな特性体のための新しいアルゴリズムが使用された。計算は21778^{個の要素を持つ体を対象とし、 214}個の要素を持つ体の127次拡張として表された。計算には220コア時間未満しかかからなかった。^[15]

^{[アップデート]}素数次数2の標数を持つ有限体における現在の記録（2014年現在）は、2014年10月17日にトルステン・クラインユンによって発表された。計算は2 ¹²⁷⁹個の要素を持つ体で行われ、線形代数計算と降下フェーズという2つの主な例外を除いて、 ^[16]で概説された経路を基本的にたどった。総実行時間は4コア年未満であった。^[17]素数次数2の標数を持つ有限体における以前の記録は、2013年4月6日にCARAMELグループによって発表された。彼らは関数体ふるいを使用して、2 ⁸⁰⁹個の要素を持つ体における離散対数を計算した。^[18]${\displaystyle \mathrm {GF} (2^{4\cdot 1223})}$

標数3の体に関する現在の記録（2016年7月現在^{[アップデート]}）は、2016年7月18日にGora Adj、Isaac Canales-Martinez、Nareli Cruz-Cortés、Alfred Menezes、Thomaz Oliveira、Francisco Rodriguez-Henriquez、およびLuis Rivera-Zamarripaによって発表されました。計算は36 ^{·509要素を持つ4841ビットの有限体で行われ、} CINVESTAVとウォータールー大学の複数のコンピューターで実行されました。合計で、約200コア年の計算時間が計算に費やされました。^[19]

標数 3 の有限体におけるこれまでの記録が発表されました。

• JouxとPierrotによるAsiacrypt 2014論文の完全版（2014年12月）^[20] 。DLPは、3796ビットの体であるGF(3 ^{5 · 479} )で解かれます。この研究では、Kummerやtwisted-Kummer特性などの体の「特別な」側面は利用されていません。計算全体に要したCPU時間は8600時間未満でした。
• 2014年2月26日、Gora Adj、Alfred Menezes、Thomaz Oliveira、Francisco Rodríguez-Henríquezによる発表。2014年1月27日の発表を更新。計算は1551ビット体GF(3 ^{6 · 163} )のDLPを解き、1201CPU時間を要した。^{[21] [22]}
• 2012年に富士通、NICT、九州大学の共同チームが、関数体ふるいのバリエーションを使用して^、36・97要素、923ビットの体で離散対数を計算し、 ^36・71要素、676ビットの体で以前の記録を大幅に上回りました[ ^{23] 。 [24]}

「中程度」のサイズの特性を持つ体では、2005 年時点で注目すべき計算には、2005 年 10 月 24 日に発表された 65537 ^{× 25要素 (401 ビット) の体と、2005 年 11 月 9 日に発表された 370801 × 30}要素 (556 ビット)の体での計算がありました。 ^[25]「中程度」の特性を持つクンマー拡大有限体の現在の記録 (2013 年現在) は、2013 年 1 月 6 日に発表されました。チームは、中程度の素数の場合の関数体ふるいの新しいバリエーションを使用して、33341353 × ⁵⁷要素 (1425 ビットの有限体) のクンマー拡大体で離散対数を計算しました。^{[26] [27]}数週間前に同じ手法が使用され、33553771 ^×47個の要素を持つクンマー拡大体（1175ビットの有限体）の離散対数を計算していた。^{[27] [28]}「中程度」の特性を持つ有限体（必ずしもクンマー拡大ではない）の現在の記録（2022年現在）は、2111023 × ⁵⁰個の要素を持つ体（1051ビットの有限体）の離散対数の計算である。^[29]このような体上の離散対数計算の以前の記録^{[30]は、297079 ×40}個の要素を持つ体（728ビットの有限体）と64373 ^×37個の要素を持つ体（592ビットの有限体）であった。これらの計算は、関数体ふるいを高速化する新しいアイデアを使用して行われた。

2014年6月25日、Razvan Barbulescu、Pierrick Gaudry、Aurore Guillevic、François Morainは、160桁の位数を持ち素体の2次拡大である有限体における離散対数の新しい計算を発表しました。^[31]使用されたアルゴリズムは、数体ふるい（NFS）であり、さまざまな変更が加えられています。合計計算時間は、CPUコア1つで68日（ふるい分け）、GPUで30時間（線形代数）に相当しました。

Certicom社は、楕円曲線暗号のチャレンジシリーズを発行しました。レベルIは109ビットと131ビットのサイズのフィールドを含みます。レベルIIは163、191、239、359ビットのサイズを含みます。レベルIIのチャレンジはすべて、現在計算上不可能であると考えられています。^[32]

達成されたレベルIの課題は以下のとおりです。^[33]

• ^{ECC2K-108 は、2 108}個の要素を持つフィールド上の Koblitz 曲線の離散対数を求めるものです。この賞は、2000 年 4 月 4 日に、Robert Harley が代表を務める約 1,300 人のグループに授与されました。彼らは、高速化機能を備えた並列化Pollard rho 法を使用しました。
• ^{ECC2-109 は、2 109}個の要素を持つフィールド上の曲線の離散対数を求めるものです。この賞は、2004 年 4 月 8 日に、Chris Monico が代表を務める約 2,600 人のグループに授与されました。彼らはまた、並列化された Pollard rho 法のバージョンも使用し、暦時間で 17 か月かかりました。
• ECCp-109 は、109 ビットの素数を法とする曲線上の離散対数を求めるものです。この賞は、2002 年 4 月 15 日に、Chris Monico が代表を務める約 10,308 人のグループに授与されました。このときも、彼らは並列化された Pollard rho 法のバージョンを使用し、暦日で 549 日を要しました。

2019 年現在、131 ビット (またはそれ以上) のチャレンジはいずれも達成されていません^{[アップデート]}。

2009年7月、Joppe W. Bos、Marcelo E. Kaihara、Thorsten Kleinjung、Arjen K. Lenstra、Peter L. Montgomeryは、楕円曲線（secp112r1 ^{[34]として知られる）上で112ビット素数を法とする離散対数計算を実行したと発表しました。この計算は、約6か月にわたって200台を超える}PlayStation 3ゲームコンソールのクラスターで行われました。彼らは、一般的な並列化バージョンのPollard rho法を使用しました。^[35]

2014 年 4 月、グラーツ工科大学の Erich Wenger 氏と Paul Wolfger 氏は、18 コアのVirtex-6 FPGAクラスターを使用して、113 ビットの Koblitz 曲線の離散対数を推定^{[注 1]} 24 日で解きました。^{[36] 2015 年 1 月、同じ研究者は、113 ビットのバイナリ フィールドで定義された楕円曲線の離散対数を解きました。10 コアの Kintex-7} FPGAクラスターを使用した場合の平均実行時間は約 82 日です。^[37]

2016年12月2日、ダニエル・J・バーンスタイン、スザンヌ・エンゲルス、ターニャ・ランゲ、ルーベン・ニーダーハーゲン、クリストフ・パー、ピーター・シュヴァーベ、ラルフ・ツィンマーマンは、ポラードのロー法の並列版の最適化されたFPGA実装を使用して、バイナリ曲線上の一般的な117.35ビット楕円曲線離散対数問題の解決策を発表しました。攻撃は64〜576個のFPGAで約6か月間並列に実行されました。^[38]

2017年8月23日、日下卓也、城一翔、生田健、Md. Al-Amin Khandaker、野上康之、上原聡、山井成善、シルヴァン・デュケーンらは、114ビットの「ペアリングフレンドリー」なBarreto-Naehrig（BN）曲線上の離散対数問題を解いたと発表しました^[39]。BN曲線の特殊な6次ねじれ特性を利用して、ポラードのロー法のランダムウォークを効率的に実行しました。実装には2000個のCPUコアが使用され、問題の解決に約6か月かかりました^{[40] 。}

2020年6月16日、Aleksander Zieniewicz (zielar) と Jean Luc Pons (JeanLucPons) は、Bitcoin Puzzle Transactions Challenge で 114 ビットの秘密鍵を解くことで、secp256k1 曲線上の 114 ビット間隔楕円曲線離散対数問題を解決したことを発表しました。新記録を樹立するために、彼らは256x NVIDIA Tesla V100 GPU プロセッサ上のPollard Kangarooをベースにした独自のソフトウェア^[41]を使用し、13 日を要しました。2 週間前には、同じ数のグラフィック カードを使用して、わずか 3 日で 109 ビット間隔の ECDLP を解決していました。

• 日付順に並べた離散対数の計算