Scholarlink

Lattice basis reduction is a powerful tool for solving lattice problems, such as the shortest vector problemShortest vector problem (SVP) that asks to find a non-zero shortest vector given a lattice basis. DeepBKZDeepBKZ is a practical refinement of the BKZ reduction algorithm that calls LLL with deep insertions every time after finding non-zero shortest vectors in a projected block. In this paper, we develop “parallel DeepBKZ 2.0”, parallelized DeepBKZ reduction using large blocksizes. It can share multiple short lattice vectors among solvers to drastically accelerate the reduction process of DeepBKZ in every solver. We report experimental results of parallel DeepBKZ 2.0 for solving several instances of the Darmstadt SVP challenge.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Parallel DeepBKZ 2.0: Development of Parallel DeepBKZ Reduction with Large Blocksizes

  • 章节

  • 出版模式：

    开放获取

  • 发表日期：

    2026年

查看全文
  • Satoshi Nakamura,
  • Nariaki Tateiwa,
  • Masaya Yasuda,
  • Katsuki Fujisawa

摘要

Lattice basis reduction is a powerful tool for solving lattice problems, such as the shortest vector problemShortest vector problem (SVP) that asks to find a non-zero shortest vector given a lattice basis. DeepBKZDeepBKZ is a practical refinement of the BKZ reduction algorithm that calls LLL with deep insertions every time after finding non-zero shortest vectors in a projected block. In this paper, we develop “parallel DeepBKZ 2.0”, parallelized DeepBKZ reduction using large blocksizes. It can share multiple short lattice vectors among solvers to drastically accelerate the reduction process of DeepBKZ in every solver. We report experimental results of parallel DeepBKZ 2.0 for solving several instances of the Darmstadt SVP challenge.