首页> 外文期刊>Algorithmica >Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials
【24h】

Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials

机译:渐进亚晶格约简和多项式分解的新复杂性

获取原文
获取原文并翻译 | 示例

摘要

We present a lattice algorithm specifically designed for some classical applications of lattice reduction. The applications are for lattice bases with a generalized knapsack-type structure, where the target vectors have bounded depth. For such applications, the complexity of the algorithm improves traditional lattice reduction by replacing some dependence on the bit-length of the input vectors by some dependence on the bound for the output vectors. If the bit-length of the target vectors is unrelated to the bit-length of the input, then our algorithm is only linear in the bit-length of the input entries, which is an improvement over the quadratic complexity floating-point LLL algorithms. To illustrate the usefulness of this algorithm we show that a direct application to factoring univariate polynomials over the integers leads to the first complexity bound improvement since 1984. A second application is algebraic number reconstruction, where a new complexity bound is obtained as well.
机译:我们提出了一种专门针对格点约简的经典应用设计的格点算法。该应用程序适用于具有广义背包型结构的晶格基础,其中目标矢量的深度是有限的。对于此类应用,算法的复杂性通过将对输入矢量的位长的某种依赖替换为对输出矢量的边界的某种依赖,从而改善了传统的晶格缩减。如果目标向量的位长与输入的位长无关,则我们的算法在输入项的位长中仅是线性的,这是对二次复杂度浮点LLL算法的改进。为了说明该算法的有效性,我们显示了直接应用整数上的一元多项式因式分解会导致自1984年以来的第一个复杂度界线的改进。第二个应用是代数数重构,其中还获得了新的复杂度界线。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号