論文の概要: MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction

• arxiv url: http://arxiv.org/abs/2606.26784v2
• Date: Wed, 01 Jul 2026 12:08:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-02 15:15:53.049553
• Title: MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction
• Title（参考訳）: MergeLLL: LLLベースの格子リダクションのための階層的除算型フレームワーク
• Authors: Niharika Gauraha,
• Abstract要約: 格子基底還元アルゴリズムは、計算数理論や格子ベースの暗号に様々な応用がある。 マージソートにおける分割・分散戦略に動機づけられたMergeLLLを提案する。 メソッドは自然に並列化可能で、効率的なマルチコアと分散実行を可能にします。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lattice basis reduction algorithms have various applications in computational number theory and lattice-based cryptography, but their complexity increases rapidly with the dimension. Motivated by the divide-and-conquer strategy of merge sort and incorporating PotLLL-style deep insertions during recombination, MergeLLL is proposed. In this framework, a lattice basis is split into sub-bases (blocks), where local reductions are performed within each block using KZ reduction, approximated in practice by BKZ with block size equal to the sublattice dimension. The full basis is then reconstructed through a hierarchical merging process. The approach focuses on improving local lattice structure before refining global basis properties. The method is naturally parallelizable, enabling efficient multicore and distributed execution. The reduction and merging steps preserve the lattice structure via unimodular transformations and admit logarithmic parallel depth. In experiments on subset-sum and NTRU-style lattices, the method is evaluated against PotLLL and BKZ 2.0, showing comparable computation time with PotLLL while achieving a lower root Hermite factor, indicating higher-quality reduced bases.
• Abstract（参考訳）: 格子基底還元アルゴリズムは計算数理論や格子ベースの暗号に様々な応用があるが、その複雑さは次元とともに急速に増大する。 マージソートとPotLLLスタイルの深い挿入を組み込んだマージソートとコンカマーの分離戦略により,mergeLLLを提案する。 このフレームワークでは、格子基底をサブベース(ブロック)に分割し、KZ還元を用いて各ブロック内で局所的な還元を行う。 完全な基盤は、階層的なマージプロセスによって再構築される。 このアプローチは、グローバル基底特性を精錬する前に局所格子構造を改善することに重点を置いている。 この方法は自然に並列化可能であり、効率的なマルチコアおよび分散実行を可能にする。 縮小と融合のステップは、一モジュラー変換を通じて格子構造を保持し、対数平行深さを許容する。 サブセットサムとNTRUスタイルの格子の実験では、PotLLLとBKZ 2.0に対して評価され、PotLLLと同等の計算時間を示しながら、低根のHermite因子を達成し、高品質な削減ベースを示す。

関連論文リスト

• An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition [0.0]
  本稿では,非負行列上に補正されたスパース低ランク特性について検討する。 本稿では,クラスタリングと圧縮タスクに有用な構造を取り入れた新しい正規化項を提案する。 我々は、任意の$Lge 1$に対して常に持つ$L$-smoothプロパティを維持しながら、対応する閉形式解を導出する。
  論文  参考訳（メタデータ） (2025-03-04T08:20:34Z)
• Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach [12.679411410749521]
  本稿では,ニューラルネットワークによる格子縮小問題に対するアルゴリズム空間のパラメータ化と,教師付きデータを持たないアルゴリズムの探索を行うことが可能であることを示す。 本研究では,一様行列の因子を出力する深層ニューラルネットワークを設計し,非直交格子基底をペナルライズして自己指導的に学習する。 提案手法は,一連のベンチマークにおいて,Lenstra-Lenstra-Lov'aszアルゴリズムに匹敵する複雑性と性能を持つアルゴリズムが得られることを示す。
  論文  参考訳（メタデータ） (2023-11-14T13:54:35Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• A Parallelizable Lattice Rescoring Strategy with Neural Language Models [62.20538383769179]
  自動音声認識のためのニューラルネットワークモデル(LM)を用いた効率的な格子相関のための後部格子拡張アルゴリズムを提案する。 スイッチボードデータセットにおける実験により,提案手法が同等の認識性能を得た。 PyTorchで訓練されたニューラル LM をKaldi との格子再構成に簡単に統合することで、並列再描画法により柔軟性が向上する。
  論文  参考訳（メタデータ） (2021-03-08T21:23:12Z)
• Feature Whitening via Gradient Transformation for Improved Convergence [3.5579740292581]
  機能白化の複雑さの欠点に対処する。 サンプル変換を重み勾配への変換によって置き換える等価な手法をBサンプルの各バッチに適用する。 CIFAR と Imagenet データセットで実証された画像分類のためのResNet ベースのネットワークを用いて提案アルゴリズムを例示する。
  論文  参考訳（メタデータ） (2020-10-04T11:30:20Z)

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

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