論文の概要: A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring

• arxiv url: http://arxiv.org/abs/2510.19390v1
• Date: Wed, 22 Oct 2025 09:06:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:15.445026
• Title: A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring
• Title（参考訳）: 格子型ファクタリングにおける最接近ベクトル問題に対する確率論的計算手法
• Authors: Max O. Al-Hasso, Marko von der Leyen,
• Abstract要約: 最も近いベクトル問題(CVP)は格子ベースの暗号における基本的な最適化問題である。 近年,格子型ファクタリングアルゴリズムにおいて,CVP近似近似近似補正のステップを組み込むことが検討されている。 本稿では,本課題に対する確率論的計算アルゴリズムの設計,素格子パラメータの議論,実験結果について述べる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The closest vector problem (CVP) is a fundamental optimization problem in lattice-based cryptography and its conjectured hardness underpins the security of lattice-based cryptosystems. Furthermore, Schnorr's lattice-based factoring algorithm reduces integer factoring (the foundation of current cryptosystems, including RSA) to the CVP. Recent work has investigated the inclusion of a heuristic CVP approximation `refinement' step in the lattice-based factoring algorithm, using quantum variational algorithms to perform the heuristic optimization. This coincides with the emergence of probabilistic computing as a hardware accelerator for randomized algorithms including tasks in combinatorial optimization. In this work we investigate the application of probabilistic computing to the heuristic optimization task of CVP approximation refinement in lattice-based factoring. We present the design of a probabilistic computing algorithm for this task, a discussion of `prime lattice' parameters, and experimental results showing the efficacy of probabilistic computing for solving the CVP as well as its efficacy as a subroutine for lattice-based factoring. The main results found that (a) this approach is capable of finding the maximal available CVP approximation refinement in time linear in problem size and (b) probabilistic computing used in conjunction with the lattice parameters presented can find the composite prime factors of a semiprime number using up to 100x fewer lattice instances than similar quantum and classical methods.
• Abstract（参考訳）: 最も近いベクトル問題(CVP)は格子ベースの暗号における基本的な最適化問題であり、その予想された硬さは格子ベースの暗号システムのセキュリティを支えている。 さらに、Schnorrの格子ベースのファクタリングアルゴリズムは、整数ファクタリング(RSAを含む現在の暗号システムの基盤)をCVPに還元する。 最近の研究は、量子変分法アルゴリズムを用いて、格子ベースのファクタリングアルゴリズムにヒューリスティックCVP近似「Refinement」ステップを組み込むことで、ヒューリスティック最適化を実現している。 これは、組合せ最適化のタスクを含むランダム化アルゴリズムのハードウェアアクセラレーターとして確率計算が出現したのと一致する。 本研究では,格子型ファクタリングにおけるCVP近似近似のヒューリスティック最適化問題に対する確率計算の適用について検討する。 本稿では,この課題に対する確率論的計算アルゴリズムの設計,「素格子」パラメータの議論,およびCVPの解法における確率論的計算の有効性,および格子ベースのファクタリングのサブルーチンとしての有効性を示す実験結果について述べる。 主な結果は (a) この問題サイズと時間線形な時間における最大可算 CVP 近似補正を求めることができる。 b) 提示された格子パラメータと合わせて用いられる確率的計算は、類似の量子および古典的手法よりも最大100倍少ない格子インスタンスを用いて半素数の合成素因子を見つけることができる。

関連論文リスト

• Are Randomized Quantum Linear Systems Solvers Practical? [0.0]
  ランダム化量子アルゴリズムは、量子シミュレーションと量子線型代数の文脈で提案されている。 ランダム化量子線形系解法における全誤差を制御する全ての関連するパラメータに明示的な境界を与える。 私たちの研究は、理論的なアルゴリズムの提案と効率的なハードウェア実装の橋渡しとして役立ちます。
  論文  参考訳（メタデータ） (2025-10-15T17:12:55Z)
• A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles [0.0]
  最も近いベクトル問題(CVP)のNP硬度は、量子セキュア暗号の重要な基盤である。 量子アルゴリズムによる最近の研究は、(制約のある)CVPインスタンスの近似を見つける可能性を示している。 この研究は、その後の因数分解の主張を考慮せずに、近似CVPに対する量子的優位性の可能性を探究する。
  論文  参考訳（メタデータ） (2025-03-11T13:06:38Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Integer Factorization through Func-QAOA [0.0]
  暗号時間整数分解のための効率的な古典的アルゴリズムは発見されていない。 本稿では,Func-QAOAによる因子化手法を提案する。
  論文  参考訳（メタデータ） (2023-09-26T18:00:25Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Selection of the Most Probable Best [2.1095005405219815]
  予測値ランキングと選択(R&S)問題では,すべてのk解のシミュレーション出力が,分布によって不確実性をモデル化可能な共通パラメータに依存する。 我々は、最も確率の高い最適解 (MPB) を、分布に関して最適である確率が最も大きい解と定義する。 最適化条件における未知の手段をその推定値に置き換えるアルゴリズムを考案し,シミュレーション予算が増加するにつれて,アルゴリズムのサンプリング比が条件を満たすことを証明した。
  論文  参考訳（メタデータ） (2022-07-15T15:27:27Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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