論文の概要: Generalized Implicit Factorization Problem
- arxiv url: http://arxiv.org/abs/2304.08718v3
- Date: Mon, 4 Mar 2024 02:56:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-17 17:20:31.180187
- Title: Generalized Implicit Factorization Problem
- Title(参考訳): 一般化帰納的因数分解問題
- Authors: Yansong Feng, Abderrahmane Nitaj, Yanbin Pan,
- Abstract要約: Implicit Factorization Problem は 5 と Ritzenhofen が PKC'09 で最初に導入した。
格子に基づくアルゴリズムを提案し,その効率を一定の条件下で解析する。
- 参考スコア(独自算出の注目度): 29.650588509354606
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Implicit Factorization Problem was first introduced by May and Ritzenhofen at PKC'09. This problem aims to factorize two RSA moduli $N_1=p_1q_1$ and $N_2=p_2q_2$ when their prime factors share a certain number of least significant bits (LSBs). They proposed a lattice-based algorithm to tackle this problem and extended it to cover $k>2$ RSA moduli. Since then, several variations of the Implicit Factorization Problem have been studied, including the cases where $p_1$ and $p_2$ share some most significant bits (MSBs), middle bits, or both MSBs and LSBs at the same position. In this paper, we explore a more general case of the Implicit Factorization Problem, where the shared bits are located at different and unknown positions for different primes. We propose a lattice-based algorithm and analyze its efficiency under certain conditions. We also present experimental results to support our analysis.
- Abstract(参考訳): Implicit Factorization Problem は 5 と Ritzenhofen が PKC'09 で最初に導入した。
この問題は、2つのRSA moduli $N_1=p_1q_1$ と $N_2=p_2q_2$ を素因子が最小有意ビット数(LSB)を共有するときに分解することを目的としている。
彼らはこの問題に対処する格子ベースのアルゴリズムを提案し、それを$k>2$ RSA moduli に拡張した。
それ以来、$p_1$と$p_2$がいくつかの重要なビット(MSB)を共有する場合や、中間ビット、MSBとLSBを同じ位置に共有する場合など、Implicit Factorization Problemのいくつかのバリエーションが研究されている。
本稿では,異なる素数に対して,共有ビットが異なる位置,未知の位置にある不特定因数分解問題のより一般的な事例について検討する。
格子に基づくアルゴリズムを提案し,その効率を一定の条件下で解析する。
分析を支援するために実験結果も提示する。
関連論文リスト
- Quantum and Classical Combinatorial Optimizations Applied to
Lattice-Based Factorization [0.046040036610482664]
格子ベースのファクタリングは、より大きな数にうまくスケールしないことが示される。
我々は、CVPの特定の事例と、分解パイプラインの他の部分に量子技術を適用する機会について検討する。
論文 参考訳(メタデータ) (2023-08-15T14:31:25Z) - Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise [1.3198689566654105]
我々は、ショアの量子ファクタリングアルゴリズムをノイズの多い量子ゲートの設定とみなす。
回転ゲートに対するランダムノイズの一般的なモデルの下では、このアルゴリズムが$pq$という形の整数を分解しないことが証明される。
さらに、確率 1 - o(1)$ over random prime pairs $(p,q)$, Shor's factoring algorithm not factor number of the form $pq$, with the level of random noise present。
論文 参考訳(メタデータ) (2023-06-15T21:55:44Z) - Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the
Cryptanalysis of pSIDH [5.398058794903461]
自己同型環問題(英語版)(IsERP)は、超特異曲線の間の同型写像の余領域の自己同型環を計算することを要求する。
次数が奇数で、多くの素因子が$O(loglog p)=$である等質性に対して、IsERPを解くための新しい量子時間アルゴリズムを導入する。
論文 参考訳(メタデータ) (2023-05-31T14:30:32Z) - HUBO and QUBO models for Prime factorization [0.0]
RSA暗号システムのセキュリティは、N=p*qを満たす素数 p と q に大数 N を分解することの難しさに基づいている。
本稿では,RSA暗号システムを脅かすことができるD-Wave量子コンピュータを用いた素因数分解法を提案する。
論文 参考訳(メタデータ) (2023-01-17T07:49:10Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - End-to-end resource analysis for quantum interior point methods and
portfolio optimization [92.13478140615481]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳(メタデータ) (2022-11-22T18:54:48Z) - An Algebraic-Geometry Approach to Prime Factorization [0.0]
素因数分解のための新しいアルゴリズムは、暗号アルゴリズムの現在の実装に実践的な影響を与える可能性がある。
n/2以上のパラメータを効率的に評価できる多様体が存在することを示す。
ある場合、 n/2 以上のパラメータが与えられたとき、効率的に点を評価できる多様体が存在することを示す。
論文 参考訳(メタデータ) (2022-09-23T15:31:07Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳(メタデータ) (2021-07-03T23:17:26Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳(メタデータ) (2020-12-01T13:53:23Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。