論文の概要: An average case efficient algorithm for solving two variable linear diophantine equations
- arxiv url: http://arxiv.org/abs/2409.14052v1
- Date: Sat, 21 Sep 2024 07:51:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-07 03:55:36.779273
- Title: An average case efficient algorithm for solving two variable linear diophantine equations
- Title（参考訳）: 2つの線形ディオファンチン方程式を解く平均ケース効率アルゴリズム
- Authors: Mayank Deora, Pinakpani Pal,
- Abstract要約: 2つの可変線形ディオファンチン方程式を解くことは、RSAや楕円曲線暗号などの多くの暗号プロトコルに応用できる。
2つの線形ディオファンチン方程式を解くために2つのアルゴリズムを再検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Solving two variable linear diophantine equations has applications in many cryptographic protocols such as RSA and Elliptic curve cryptography. Extended euclid's algorithm is the most widely used algorithm to solve these equations. We revisit two algorithms to solve two variable linear diophantine equations. For one of them, we do fine-grained analysis of the number of recursive calls and find a periodic function, which represents the number of recursive calls. We find the period and use it to derive an accurate closed form expression for the average number of recursive calls incurred by that algorithm. In the process of this derivation we get an upper bound on the average number of recursive calls, which depends on the intermediate values observed during the execution of algorithm. We propose an iterative version of the algorithm. While implementation of our algorithm, we verify a well known result from number theory about the probability of two random integers being coprime. Due to that result, our algorithm encounters an additional constraint for approximately 40% times. On almost all of these constrained inputs i.e. on nearly 100 % of them the algorithm outperforms two existing algorithms.
- Abstract（参考訳）: 2つの可変線形ディオファンチン方程式を解くことは、RSAや楕円曲線暗号などの多くの暗号プロトコルに応用できる。
拡張ユークリッドのアルゴリズムは、これらの方程式を解くのに最も広く使われているアルゴリズムである。
2つの線形ディオファンチン方程式を解くために2つのアルゴリズムを再検討する。
そのうちの1つでは、再帰呼び出し数を詳細に分析し、再帰呼び出しの数を表す周期関数を求める。
我々はこの周期を見つけ、そのアルゴリズムで得られた再帰呼び出しの平均数に対して正確な閉形式式を導出する。
この導出の過程では、アルゴリズムの実行中に観測される中間値に依存する再帰呼び出しの平均値に上限が与えられる。
本稿では,アルゴリズムの反復バージョンを提案する。
アルゴリズムの実装中に、2つのランダム整数の確率が相反する確率に関する数論からよく知られた結果を検証する。
その結果,アルゴリズムは約40%の制約を課すことができた。
これらの制約された入力のほとんどすべて、すなわち約100%の入力に対して、アルゴリズムは2つの既存のアルゴリズムより優れている。
関連論文リスト
- Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field [8.950235011733273]
有限素体における離散対数問題の解法として、二重指数計算アルゴリズムを提案する。
我々のアルゴリズムは指数計算アルゴリズムよりも高速である。
我々のアルゴリズムは指数計算アルゴリズムよりも一般的である。
論文 参考訳（メタデータ） (2024-09-13T12:41:32Z) - A Quantum Diophantine Equation Solution Finder [0.0]
Groverのアルゴリズムは量子検索アルゴリズムであり、リスト内のマーク付きインデックスを非常に効率的に見つけることができる。
指数をディオファンチン方程式の整数変数として扱うことで、グロバーのアルゴリズムは古典的な方法よりも効率的にブルート力の解を見つけることができる。
論文 参考訳（メタデータ） (2024-08-21T13:31:32Z) - 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) - An Efficient Summation Algorithm for the Accuracy, Convergence and
Reproducibility of Parallel Numerical Methods [0.0]
我々は浮動小数点数の列をまとめる新しい並列アルゴリズムを導入した。
プロセッサ数で簡単にスケールアップできるこのアルゴリズムは、まず同じ指数の数を加算する。
この記事では、いくつかの特性に関して、その効率を広範囲に分析する。
論文 参考訳（メタデータ） (2022-05-11T08:31:48Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
本稿では,マルチカット問題(マグニチュード相関クラスタリング)に対する高並列原始双対アルゴリズムを提案する。
我々のアルゴリズムは、最適距離を推定する原始解と双対下界を生成する。
最大$mathcalO(108)$変数を数秒で、小さな原始双対ギャップで、非常に大規模なベンチマーク問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-04T10:33:59Z) - 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 Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。