論文の概要: Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field
- arxiv url: http://arxiv.org/abs/2409.08784v1
- Date: Fri, 13 Sep 2024 12:41:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-16 16:39:02.413901
- Title: Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field
- Title（参考訳）: Double Index Calculus Algorithm:finite Prime Fieldにおける離散対数問題の高速解法
- Authors: Wen Huang, Zhishuo Zhang, Weixin Zhao, Jian Peng, Yongjian Liao, Yuyu Wang,
- Abstract要約: 有限素体における離散対数問題の解法として、二重指数計算アルゴリズムを提案する。
我々のアルゴリズムは指数計算アルゴリズムよりも高速である。
我々のアルゴリズムは指数計算アルゴリズムよりも一般的である。
- 参考スコア（独自算出の注目度）: 8.950235011733273
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Solving the discrete logarithm problem in a finite prime field is an extremely important computing problem in modern cryptography. The hardness of solving the discrete logarithm problem in a finite prime field is the security foundation of numerous cryptography schemes. In this paper, we propose the double index calculus algorithm to solve the discrete logarithm problem in a finite prime field. Our algorithm is faster than the index calculus algorithm, which is the state-of-the-art algorithm for solving the discrete logarithm problem in a finite prime field. Empirical experiment results indicate that our algorithm could be more than a 30-fold increase in computing speed than the index calculus algorithm when the bit length of the order of prime field is 70 bits. In addition, our algorithm is more general than the index calculus algorithm. Specifically, when the base of the target discrete logarithm problem is not the multiplication generator, the index calculus algorithm may fail to solve the discrete logarithm problem while our algorithm still can work.
- Abstract（参考訳）: 有限素体における離散対数問題を解くことは、現代の暗号における非常に重要な計算問題である。
有限素体における離散対数問題を解くことの難しさは、多数の暗号スキームのセキュリティ基盤である。
本稿では,有限素体における離散対数問題の解法として,二重指数計算アルゴリズムを提案する。
このアルゴリズムは有限素体における離散対数問題を解くための最先端のアルゴリズムである指数計算アルゴリズムよりも高速である。
実験結果から,素数順序のビット長が70ビットである場合,本アルゴリズムは指数計算アルゴリズムよりも30倍以上の計算速度が増大する可能性が示唆された。
さらに,本アルゴリズムは指数計算アルゴリズムよりも汎用性が高い。
具体的には、対象とする離散対数問題の基底が乗算生成元ではない場合、我々のアルゴリズムが動作する間、インデックス計算アルゴリズムは離散対数問題の解決に失敗する可能性がある。
関連論文リスト
- An average case efficient algorithm for solving two variable linear diophantine equations [0.0]
2つの可変線形ディオファンチン方程式を解くことは、RSAや楕円曲線暗号などの多くの暗号プロトコルに応用できる。
2つの線形ディオファンチン方程式を解くために2つのアルゴリズムを再検討する。
論文 参考訳（メタデータ） (2024-09-21T07:51:12Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - GreedyML: A Parallel Algorithm for Maximizing Submodular Functions [2.9998889086656586]
分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。
我々の研究は、データ要約、機械学習、グラフスカラー化といった分野における実践的な応用のために、大規模データセットのサブモジュラー最適化問題を解決する必要性によって動機付けられている。
論文 参考訳（メタデータ） (2024-03-15T14:19:09Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Minors solve the elliptic curve discrete logarithm problem [0.0]
本稿では楕円曲線離散対数問題の解法を検討する。
初期の研究に続いて、楕円曲線が定義される同じ有限体上の行列の零部分を求めることでこの問題を解こうとした。
論文 参考訳（メタデータ） (2023-10-06T10:05:25Z) - Quantum optimization algorithm based on multistep quantum computation [0.0]
本稿では,多段階量子計算に基づく関数の最小値を求める量子アルゴリズムを提案する。
このアルゴリズムでは、問題の探索空間の次元を指数関数的に段階的に減らすことができる。
連続的なテスト関数のアルゴリズムを検証した。
論文 参考訳（メタデータ） (2023-06-30T01:58:23Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - An integer factorization algorithm which uses diffusion as a
computational engine [0.0]
我々は、素数でも素数でもないと仮定される整数$N$の因子を計算するアルゴリズムを開発する。
比較すると、ショアのアルゴリズムは量子コンピュータ上での最大$O(log N)2log (log N) log (log log N)$quantum stepsで使用されることが知られている。
論文 参考訳（メタデータ） (2021-04-23T14:11:33Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient improper learning for online logistic regression [68.8204255655161]
サンプル数 n の対数的後悔を持つ任意の正則アルゴリズムは、必然的に B の指数乗法定数を損なうことが知られている。
本研究では、対数的後悔を保ちながら、この指数定数を回避する効率的な不適切なアルゴリズムを設計する。
シュロゲート損失を伴う正規化経験的リスク最小化に基づく新しいアルゴリズムは、O(B log(Bn))として、オーダーO(d2)の1回あたりの時間複雑度で、後悔のスケーリングを満足させる。
論文 参考訳（メタデータ） (2020-03-18T09:16:14Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。