适用范围：计算格与格密码中的格基约化及近似算法，使用欧氏范数。整理日期：2026-10-16。 前置笔记：02 基本区域、格行列式与正交化、04 基本计算格问题：SVP、CVP 与 SIVP。
本篇的核心是：通过保持格不变的换基操作，得到满足局部约化条件的基，再由这些条件推出短向量的近似保证。
约定：输入 \(B=[b_1,\ldots,b_n]\in\mathbb Z^{m\times n}\) 列满秩，\(\Lambda=\mathcal L(B)\)，使用欧氏范数。\(b_i^*\) 和 \(\mu_{i,j}\) 沿用 Gram–Schmidt 记号：
格基约化的目标#
格基约化通过幺模变换
在同一个格中寻找更便于计算的基。
因此，约化过程中 \(\Lambda\)、\(\det\Lambda\) 和各个 \(\lambda_i(\Lambda)\) 都保持不变，改变的是基向量的长度及相互位置。
LLL 输出原格的另一组基；Gram–Schmidt 正交化提供衡量和调整这组基所需的辅助量。
LLL 约化基的两个条件#
固定参数
常用理论取值为 \(\delta=3/4\)。
一组基称为 \(\delta\)-LLL 约化基，需要同时满足：
尺寸约化条件
它控制每个基向量沿前面正交方向的投影系数。
Lovász 条件
结合尺寸约化条件可得
即相邻正交分量的长度不能下降过快。当 \(\delta=3/4\) 时，
[1，第 2 页，Definition 2 与 Remark 3]
算法流程：尺寸约化与交换#
尺寸约化使用整数列操作：
这里减去的是整数倍的基向量 \(b_j\)，因此保持原格不变。
下面采用便于理解的伪代码，运算按精确有理数理解：
输入：整数格基 B，固定参数 1/4 < δ < 1
重复：
计算当前基的 Gram–Schmidt 向量 b_i*
对 i = 2, ..., n：
对 j = i-1, ..., 1： # 按逆序处理
q ← round(〈b_i, b_j*〉 / ||b_j*||²)
b_i ← b_i - q·b_j # 使用当前的 b_i
根据当前基重新计算投影系数 μ
如果所有相邻向量均满足 Lovász 条件：
返回 B
选择一处不满足条件的下标 k
交换 b_{k-1} 与 b_kround 表示取最近整数，恰好位于两个整数中间时任选其一。
尺寸约化不改变 Gram–Schmidt 向量；逆序处理 \(j\) 可以保持已经处理好的较大下标投影系数。交换会改变正交化结果，因此需要重新计算并继续约化。两类操作都是幺模换基。[1，第 3—5 页，§2、Lemma 3]
一个简短例子#
取
原基行列式为 \(1\)，生成 \(\mathbb Z^2\)。
首先，
在二维情况下，Lovász 条件右侧就是当前的 \(\|b_2\|_2^2\)。此时
因此交换两个向量，得到
再做一次尺寸约化：
最终得到基 \((-1,0),(0,1)\)，满足两项约化条件，生成的格仍为 \(\mathbb Z^2\)。
为什么能够终止，并在多项式时间内完成#
记前 \(k\) 个基向量构成的矩阵为 \(B_k=[b_1,\ldots,b_k]\)，定义势函数
$$ \Phi(B)#
\prod_{k=1}^{n}\det(B_k^TB_k)#
\prod_{i=1}^{n}|b_i^*|_2^{,2(n-i+1)}. $$
整数基的每个 Gram 行列式都是正整数，所以 \(\Phi(B)\ge1\)。
- 尺寸约化保持 \(\Phi(B)\) 不变。
- 每次因违反 Lovász 条件而交换，都有 \(\Phi(B_{\mathrm{new}})<\delta\,\Phi(B_{\mathrm{old}})\)。
因此交换次数有限。对固定 \(\delta<1\)，初始 \(\log\Phi(B)\) 受输入比特长度的多项式控制；再结合中间数值比特长度的界，可得 LLL 的总运行时间为输入长度的多项式。
这里需要同时控制操作次数和操作数的比特长度。[2，PDF 第 6—8 页，§3.1—§3.2]
LLL 提供什么保证#
令
对输出的 \(\delta\)-LLL 约化基，有
以及
因此，取第一列即可得到近似 SVP 解；取整组基即可得到近似 SIVP 解。
当 \(\delta=3/4\) 时，\(\alpha=2\)，两者的近似因子为
此外还有与格行列式的直接联系：
[2，PDF 第 2—3 页，Theorem 3]
第一项保证可以直接衔接第三篇的下界：
[1，第 3 页，Claim 1]
多项式时间描述的是运行时间；这里保证的近似因子仍随维数指数增长。 LLL 不保证找到精确最短向量。
来源与阅读位置#
- Oded Regev，Lattices in Computer Science，Lecture 2: LLL Algorithm。课程标注 Fall 2004，PDF 标注最后更新于 2013-02-05。主阅读位置为 §1—§3、第 2—8 页：第 2 页 Definition 2 与 Remark 3、第 3 页 Claim 1、第 3—5 页算法与正确性、第 5—8 页运行时间分析。原文
- Daniele Micciancio，Basis Reduction，PDF 页首标注 Fall 2017，由 2019 年课程页链接。辅助阅读 §1、§3：PDF 第 2—3 页近似保证与 Theorem 3、第 6—8 页算法及势函数与比特复杂度分析。原文
来源于 2026-10-16 核对，正文按已确认的草稿整理。
下一篇计划：《06 Babai 最近平面算法与近似 CVP》，讨论如何利用 LLL 约化基，为给定目标寻找附近的格点。