LLL格约减算法由Arjen Lenstra，Hendrik Lenstra以及László Lovász三人于1982年提出的一种在多项式时间内求解格中的近似正交基的算法。由于格的性质，如果能够通过某种方式求得一个格的正交基，那么求解最近向量问题（CVP）与最短向量问题（SVP）都将是十分容易的。
事实上，在某种情况下，我们可以把LLL算法看作是对Gauss约减算法的一种拓展，因为Gauss约减算法解决了求解二维格中的一个近似正交基问题，而LLL算法则将这个维度拓展到了维。
LLL格约减算法的定义
其中要注意的一点是，对于罗瓦兹条件，其可以有多种表达形式，其另一种同样常见且正确的表达方式为。
对于LLL约减算法的定义，用更直白的语言来说，给定一个格的一组基
，
是其经过施密特正交化后的一组基，那么我们说，如果对于基
，其满足以上两个条件（尺度条件与罗瓦兹条件），那么便认为基
是经LLL约减后的一组基。
经过LLL格约减算法后得到的一组基有着一些良好的性质，利用这些性质我们可以很容易地求解某些问题，例如，通过使用LLL格约减算法可以在一个令密钥持有者十分不安的时间内，破解那些使用基于背包密码体制问题的密码系统密钥。
LLL格约减算法的计算
LLL格约减算法的伪代码如下所示：
该算法没有什么难点，只要按照步骤走，就可以得到一组LLL的近似正交基。但是需要注意的是Gram-Shimidt正交化的时机。在实际使用该算法时，并不是在一开始计算一次Gram-Schimidt就可以了，而是在每一次步骤（这里的步骤指的是k的循环）的开始，需要重新计算一次当前基(v1,v2,v3,...,vn)的Gram-Schimidt正交化基。
考虑到在许多写LLL算法的博客都没有给出LLL算法的例子，我这里便给出一个使用LLL算法的例子，供大家参考，该例子来源于Youtube链接。
问题：给定格，其一组基
，利用LLL算法求其约减后的一组基。
