論文の概要: An average case efficient algorithm for solving two-variable linear Diophantine equations

• arxiv url: http://arxiv.org/abs/2409.14052v3
• Date: Wed, 21 May 2025 07:04:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-22 15:42:56.90907
• Title: An average case efficient algorithm for solving two-variable linear Diophantine equations
• Title（参考訳）: 2変数線形ディオファント方程式の解法における平均ケース効率アルゴリズム
• Authors: Mayank Deora, Pinakpani Pal,
• Abstract要約: 2変数線型ディオファント方程式を解くために2つのアルゴリズムを再検討する。 拡張ユークリッドアルゴリズムの反復バージョンを提案する。 我々のアルゴリズムによる平均的な反復回数は、既存の2つのアルゴリズムよりも少ないことがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving two-variable linear Diophantine equations has application in many cryptographic protocols such as RSA and Elliptic curve cryptography. The 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. We write the iterative version of one of the revisited algorithms. For another, we do a fine-grained analysis of the number of recursive calls and arrive at a periodic function that 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. We find multiple loose upper bounds on the average number of recursive calls in different cases based on whether a solution exists or not. If for a fixed value of $a,b$ and a varying $c$, an equation $ax+by=c$ (where $a>b$) is solvable, then we can find the solution in $O\left(\frac{\log b}{gcd(a,b)}\right)$ average number of recursion or steps. We computationally evaluate this bound as well as one more upper bound and compare them with the average number of recursive calls in Extended Euclid's algorithm on a number of random $ n$-bit inputs. We observe that the average number of iterations in the analyzed algorithm decreases with an increase in $gcd(a,b)$. We propose an iterative version of the algorithm. We implement this algorithm and find that the average number of iterations by our algorithm is less than that of two existing algorithms.
• Abstract（参考訳）: 2変数線形ディオファントス方程式の解法はRSAや楕円曲線暗号などの多くの暗号プロトコルに適用できる。 拡張ユークリッドのアルゴリズムは、これらの方程式を解くのに最も広く用いられるアルゴリズムである。 2変数線型ディオファント方程式を解くために2つのアルゴリズムを再検討する。 再検討したアルゴリズムの反復バージョンを記述します。 別の例として、再帰呼び出しの数を詳細に分析し、再帰呼び出しの数を表す周期関数に到達する。 我々はこの周期を見つけ、そのアルゴリズムで得られた再帰呼び出しの平均数に対して正確なクローズドフォーム式を導出する。 解が存在するか否かによって異なるケースで、平均再帰呼び出し数について、複数のゆるやかな上限を求める。 a,b$ の固定値と様々な $c$ に対して、方程式 $ax+by=c$ (ここで $a>b$) が解けるなら、その解は $O\left(\frac{\log b}{gcd(a,b)}\right)$ 平均再帰数やステップ数で見つかる。 我々は、この境界と1つの上界を計算的に評価し、無作為な$n$-bit入力で拡張ユークリッドのアルゴリズムにおける再帰呼び出しの平均値と比較する。 解析アルゴリズムにおける平均反復回数は、$gcd(a,b)$の増加とともに減少する。 本稿では,アルゴリズムの反復バージョンを提案する。 このアルゴリズムを実装した結果,提案アルゴリズムの繰り返し回数は既存の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)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Efficient Strongly Polynomial Algorithms for Quantile Regression [12.772027028644041]
  量子回帰(QR)の古典的手法を再考する 本稿では,様々な設定に対して,QRに対して高効率な古典的アルゴリズムを提案する。 2次元QRでは、$k$-setという幾何学的概念に結びつくため、$mathcalO(n4/3 polylog(n))$の最悪の時間複雑性を持つアルゴリズムを提案する。 2次元に対して$mathcalO(nlog2(n))$の期待時間複雑性を持つランダム化QRも提案する。
  論文  参考訳（メタデータ） (2023-07-14T03:07:42Z)
• An Efficient Summation Algorithm for the Accuracy, Convergence and Reproducibility of Parallel Numerical Methods [0.0]
  我々は浮動小数点数の列をまとめる新しい並列アルゴリズムを導入した。 プロセッサ数で簡単にスケールアップできるこのアルゴリズムは、まず同じ指数の数を加算する。 この記事では、いくつかの特性に関して、その効率を広範囲に分析する。
  論文  参考訳（メタデータ） (2022-05-11T08:31:48Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• 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)
• Well Separated Pair Decomposition and power weighted shortest path metric algorithm fusion [0.0]
  私たちは、あるポイントセットで$s$-wellの分離ペアを$mathbbrn$, $n$$$>$$1で計算するアルゴリズムを考えています。 また、ダイクストラのアルゴリズムの置換であるアルゴリズムについても検討し、特定のパワー重み付き最短経路メトリックを用いてk$-nearestの隣人を計算し、$mathbbrn$,$n$$$$$$$$$$で計算する。
  論文  参考訳（メタデータ） (2021-03-20T17:38:13Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• How Do You Want Your Greedy: Simultaneous or Repeated? [41.440943886672855]
  制約付き部分モジュラーユリアに対する決定論的アルゴリズムであるSimultaneousGreedysを提案する。 また、これらのアルゴリズムを実装するパッケージであるSubmodularGreedyも提示する。
  論文  参考訳（メタデータ） (2020-09-29T13:34:09Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。