...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Designs, Codes and Crytography >PotLLL: a polynomial time version of LLL with deep insertions
【24h】

PotLLL: a polynomial time version of LLL with deep insertions

机译：PotLLL：具有深度插入的LLL的多项式时间版本

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Lattice reduction algorithms have numerous applications in number theory, algebra, as well as in cryptanalysis. The most famous algorithm for lattice reduction is the LLL algorithm. In polynomial time it computes a reduced basis with provable output quality. One early improvement of the LLL algorithm was LLL with deep insertions (DeepLLL). The output of this version of LLL has higher quality in practice but the running time seems to explode. Weaker variants of DeepLLL, where the insertions are restricted to blocks, behave nicely in practice concerning the running time. However no proof of polynomial running time is known. In this paper PotLLL, a new variant of DeepLLL with provably polynomial running time, is presented. We compare the practical behavior of the new algorithm to classical LLL, BKZ as well as blockwise variants of DeepLLL regarding both the output quality and running time.
机译：格简化算法在数论，代数以及密码分析中具有众多应用。用于减少晶格的最著名算法是LLL算法。在多项式时间内，它以可证明的输出质量计算出简化的基础。 LLL算法的一项早期改进是具有深度插入的LLL（DeepLLL）。在实践中，此版本的LLL的输出质量更高，但是运行时间似乎激增。 DeepLLL的较弱变体（其中插入仅限于块）在实践中表现出与运行时间有关的良好表现。但是，尚无多项式运行时间的证明。在本文中，PotLLL是DeepLLL的新变体，具有可证明的多项式运行时间。在输出质量和运行时间方面，我们将新算法与经典LLL，BKZ以及DeepLLL的逐块变体的实际行为进行了比较。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号