論文の概要: A parameter study for LLL and BKZ with application to shortest vector problems
- arxiv url: http://arxiv.org/abs/2502.05160v1
- Date: Fri, 07 Feb 2025 18:41:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-10 14:54:57.574340
- Title: A parameter study for LLL and BKZ with application to shortest vector problems
- Title（参考訳）: LLLとBKZのパラメータスタディと最短ベクトル問題への応用
- Authors: Tobias Köppl, René Zander, Louis Henkel, Nikolay Tcholtchev,
- Abstract要約: 与えられたSVPを単純化するために使用できる2つのよく知られたアルゴリズムは、Lenstra-Lenstra-Lov'asz (LLL)アルゴリズムとBlock Korkine-Zolotarev (BKZ)アルゴリズムである。
異なるサイズとモジュラリングを持つSVPに対する両アルゴリズムの性能について検討する。
- 参考スコア（独自算出の注目度）: 0.20971479389679337
- License:
- Abstract: In this work, we study the solution of shortest vector problems (SVPs) arising in terms of learning with error problems (LWEs). LWEs are linear systems of equations over a modular ring, where a perturbation vector is added to the right-hand side. This type of problem is of great interest, since LWEs have to be solved in order to be able to break lattice-based cryptosystems as the Module-Lattice-Based Key-Encapsulation Mechanism published by NIST in 2024. Due to this fact, several classical and quantum-based algorithms have been studied to solve SVPs. Two well-known algorithms that can be used to simplify a given SVP are the Lenstra-Lenstra-Lov\'asz (LLL) algorithm and the Block Korkine-Zolotarev (BKZ) algorithm. LLL and BKZ construct bases that can be used to compute or approximate solutions of the SVP. We study the performance of both algorithms for SVPs with different sizes and modular rings. Thereby, application of LLL or BKZ to a given SVP is considered to be successful if they produce bases containing a solution vector of the SVP.
- Abstract（参考訳）: 本研究では,最短ベクトル問題 (SVP) の解を誤り問題 (LWE) による学習の観点から検討する。
LWE はモジュラー環上の方程式の線型系であり、摂動ベクトルが右辺に追加される。
このタイプの問題は、2024年にNISTが発表したモジュール格子ベースの鍵カプセル化機構として格子ベースの暗号システムを破るために、LWEを解く必要があるため、非常に興味深い問題である。
この事実により、SVPを解くために古典的および量子ベースのアルゴリズムがいくつか研究されている。
与えられたSVPを単純化するために使用できる2つのよく知られたアルゴリズムは、Lenstra-Lenstra-Lov\'asz (LLL)アルゴリズムとBlock Korkine-Zolotarev (BKZ)アルゴリズムである。
LLLとBKZは、SVPの解を計算または近似するために使用できる。
異なるサイズとモジュラリングを持つSVPに対する両アルゴリズムの性能について検討する。
これにより、与えられた SVP に対する LLL あるいは BKZ の応用は、SVP の解ベクトルを含む基底を生成すれば成功すると考えられる。
関連論文リスト
- A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。
我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。
我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
論文 参考訳（メタデータ） (2024-08-15T05:11:35Z) - On the Design and Analysis of LLM-Based Algorithms [74.7126776018275]
大規模言語モデル(LLM)はアルゴリズムのサブルーチンとして使用される。
LLMは素晴らしい経験的成功を収めた。
提案フレームワークは,LLMアルゴリズムの進歩を約束する。
論文 参考訳（メタデータ） (2024-07-20T07:39:07Z) - An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
本稿では,最近のアディバティック・インスパイアされたQLSAの進歩に基づく量子アルゴリズムを提案する。
実装の全体的な複雑さは、その次元において多対数的であることを厳密に示します。
論文 参考訳（メタデータ） (2024-03-28T20:37:32Z) - Deep Learning Assisted Multiuser MIMO Load Modulated Systems for
Enhanced Downlink mmWave Communications [68.96633803796003]
本稿では, マルチユーザ負荷変調アレイ (MU-LMA) に着目し, マイクロウェーブ (mmWave) マルチインプット・マルチアウトプット (MIMO) システムにおいて, マルチユーザ負荷変調アレイ (MU-LMA) の小型化とコスト削減を図っている。
ダウンリンクMU-LMAの既存のプリコーディングアルゴリズムは、自由度と複雑なシステム構成の低下に悩まされるサブアレイ構造化(SAS)送信機に依存している。
本稿では,FAS (Full-array Structured) 送信機を用いたMU-LMAシステムを提案し,それに応じて2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-11-08T08:54:56Z) - Online Learning Quantum States with the Logarithmic Loss via VB-FTRL [1.8856444568755568]
対数損失を伴う量子状態のオンライン学習(LL-OLQS)は、30年以上にわたってオンライン学習において古典的なオープンな問題である。
本稿では,LL-OLQS に対する VB-FTRL を適度な計算量で一般化する。
それぞれのアルゴリズムは半定値プログラムで構成されており、例えば、切断平面法によって時間内に実装することができる。
論文 参考訳（メタデータ） (2023-11-06T15:45:33Z) - AMS-Net: Adaptive Multiscale Sparse Neural Network with Interpretable
Basis Expansion for Multiphase Flow Problems [8.991619150027267]
本研究では、物理過程の学習に応用可能な適応スパース学習アルゴリズムを提案し、大きなスナップショット空間を与えられた解のスパース表現を得る。
基本関数の情報は損失関数に組み込まれており、複数の時間ステップにおけるダウンスケール縮小次数解と参照解との差を最小限に抑える。
複雑なアプリケーションにおける提案手法の有効性と解釈性を示すため, 2相多相流問題に対してより数値的な実験を行った。
論文 参考訳（メタデータ） (2022-07-24T13:12:43Z) - Optimization-based Block Coordinate Gradient Coding for Mitigating
Partial Stragglers in Distributed Learning [58.91954425047425]
本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。
L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
論文 参考訳（メタデータ） (2022-06-06T09:25:40Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - Hybrid algorithms to solve linear systems of equations with limited
qubit resources [7.111403318486868]
古典的手法を用いた複雑性は方程式のサイズとともに線形に増加する。
Harrowらによって提案されたHHLアルゴリズムは、最も優れた古典的アルゴリズムと比較して指数加速度を達成する。
本稿では,反復位相推定アルゴリズムに基づいて3つのハイブリッド反復位相推定アルゴリズム(HIPEA)を設計する。
論文 参考訳（メタデータ） (2021-06-29T15:10:55Z) - Covariance-Free Sparse Bayesian Learning [62.24008859844098]
共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。
私たちの手法は、既存のベースラインよりも数千倍も高速です。
我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
論文 参考訳（メタデータ） (2021-05-21T16:20:07Z) - Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。
我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
論文 参考訳（メタデータ） (2021-05-18T05:23:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。