主题
Search

LLL 算法

一种格约化算法，以发现者 Lenstra、Lenstra 和 Lovasz (1982) 的名字命名，该算法产生“短”向量的格基。Lenstra 等人 (1982) 注意到，该算法可以用于获得单变量多项式的因子，这相当于确定整数关系。然而，该算法的这种应用，后来成为其主要应用之一，在最初的论文中并未强调。

有关 LLL 算法的复杂度分析，请参见 Storjohann (1996)。

Wolfram 语言命令LatticeReduce[矩阵] 实现了 LLL 算法以执行格约化。Wolfram 语言的实现要求输入由有理数组成，因此Rationalize可能需要首先调用。

最近，已经开发了其他算法，例如 PSLQ，它可能比 LLL 快得多，用于查找整数关系。PSLQ 实现其性能是因为巧妙的技术允许在许多中间步骤中使用机器算术，而 LLL 必须使用适度的精度（虽然通常不如 HJLS 算法）。

另请参见

Ferguson-Forcade 算法, HJLS 算法, 整数关系, 格约化, PSLQ 算法, PSOS 算法

使用 Wolfram|Alpha 探索

参考文献

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; 和 Moll, V. H. "整数关系检测"。§2.2 in 《实验数学实践》。Wellesley, MA: A K Peters, pp. 29-31, 2007。Borwein, J. 和 Bailey, D. 《实验数学：21 世纪的似真推理》。Wellesley, MA: A K Peters, pp. 51-52, 2003。Borwein, J. M. 和 Corless, R. M. "实验数学的新兴工具"。Amer. Math. Monthly 106, 899-909, 1999。Borwein, J. M. 和 Lisonek, P. "整数关系算法的应用"。Disc. Math. 217, 65-82, 2000。实验与构造数学中心。"整数关系"。http://www.cecm.sfu.ca/projects/IntegerRelations/。Cohen, H. 《计算代数数论课程》。New York: Springer-Verlag, 1993。Lenstra, A. K.; Lenstra, H. W.; 和 Lovasz, L. "有理系数多项式的因式分解"。Math. Ann. 261, 515-534, 1982。Matthews, K. "Keith Matthews 的 LLL 页面"。http://www.numbertheory.org/lll.html。Mignotte, M. 《计算机代数数学》。New York: Springer-Verlag, 1991。Storjohann, A. "更快的整数格基约化算法"。技术报告 249. Zurich, Switzerland: Department Informatik, ETH. 1996 年 7 月 30 日。Zimmerman, P. "使用精确多精度算术的 LLL"。http://www.loria.fr/~zimmerma/free/lll.c。

在 Wolfram|Alpha 中引用

LLL 算法

请引用为

Weisstein, Eric W. "LLL 算法"。来自 MathWorld--Wolfram Web 资源。https://mathworld.net.cn/LLLAlgorithm.html

主题分类