# 05 格基约化与 LLL 算法

适用范围：计算格与格密码中的格基约化及近似算法，使用欧氏范数。整理日期：2026-10-16。
前置笔记：[02 基本区域、格行列式与正交化](/knowledge/fundamental-region-and-orthogonalization/)、[04 基本计算格问题：SVP、CVP 与 SIVP](/knowledge/svp-cvp-and-sivp/)。

本篇的核心是：通过保持格不变的换基操作，得到满足局部约化条件的基，再由这些条件推出短向量的近似保证。

约定：输入 $B=[b_1,\ldots,b_n]\in\mathbb Z^{m\times n}$ 列满秩，$\Lambda=\mathcal L(B)$，使用欧氏范数。$b_i^*$ 和 $\mu_{i,j}$ 沿用 Gram–Schmidt 记号：

$$
b_i=b_i^*+\sum_{j<i}\mu_{i,j}b_j^*.
$$

## 格基约化的目标

格基约化通过幺模变换

$$
B'=BU,\qquad U\in\mathrm{GL}_n(\mathbb Z),
$$

在同一个格中寻找更便于计算的基。

因此，约化过程中 $\Lambda$、$\det\Lambda$ 和各个 $\lambda_i(\Lambda)$ 都保持不变，改变的是基向量的长度及相互位置。

LLL 输出原格的另一组基；Gram–Schmidt 正交化提供衡量和调整这组基所需的辅助量。

## LLL 约化基的两个条件

固定参数

$$
\frac14<\delta<1,
$$

常用理论取值为 $\delta=3/4$。

一组基称为 **$\delta$-LLL 约化基**，需要同时满足：

**尺寸约化条件**

$$
\boxed{
|\mu_{i,j}|\le\frac12,\qquad j<i
}.
$$

它控制每个基向量沿前面正交方向的投影系数。

**Lovász 条件**

$$
\boxed{
\delta\|b_{k-1}^*\|_2^2
\le
\|b_k^*\|_2^2
+\mu_{k,k-1}^2\|b_{k-1}^*\|_2^2,
\qquad 2\le k\le n
}.
$$

结合尺寸约化条件可得

$$
\|b_k^*\|_2^2
\ge
\left(\delta-\frac14\right)\|b_{k-1}^*\|_2^2.
$$

即相邻正交分量的长度不能下降过快。当 $\delta=3/4$ 时，

$$
\|b_k^*\|_2^2\ge\frac12\|b_{k-1}^*\|_2^2.
$$

[1，第 2 页，Definition 2 与 Remark 3]

## 算法流程：尺寸约化与交换

尺寸约化使用整数列操作：

$$
q=\operatorname{round}(\mu_{i,j}),
\qquad
b_i\leftarrow b_i-qb_j.
$$

这里减去的是整数倍的基向量 $b_j$，因此保持原格不变。

下面采用便于理解的伪代码，运算按精确有理数理解：

```text
输入：整数格基 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_k
```

round 表示取最近整数，恰好位于两个整数中间时任选其一。

尺寸约化不改变 Gram–Schmidt 向量；逆序处理 $j$ 可以保持已经处理好的较大下标投影系数。交换会改变正交化结果，因此需要重新计算并继续约化。两类操作都是幺模换基。[1，第 3—5 页，§2、Lemma 3]

## 一个简短例子

取

$$
b_1=(2,1),\qquad b_2=(3,2),\qquad \delta=\frac34.
$$

原基行列式为 $1$，生成 $\mathbb Z^2$。

首先，

$$
\mu_{2,1}=\frac{8}{5},
\qquad
b_2\leftarrow b_2-2b_1=(-1,0).
$$

在二维情况下，Lovász 条件右侧就是当前的 $\|b_2\|_2^2$。此时

$$
\frac34\|b_1\|_2^2=\frac{15}{4}>1=\|b_2\|_2^2,
$$

因此交换两个向量，得到

$$
b_1=(-1,0),\qquad b_2=(2,1).
$$

再做一次尺寸约化：

$$
b_2\leftarrow b_2+2b_1=(0,1).
$$

最终得到基 $(-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 提供什么保证

令

$$
\alpha=\frac{1}{\delta-\frac14}.
$$

对输出的 $\delta$-LLL 约化基，有

$$
\boxed{
\|b_1\|_2
\le
\alpha^{(n-1)/2}\lambda_1(\Lambda)
},
$$

以及

$$
\boxed{
\max_i\|b_i\|_2
\le
\alpha^{(n-1)/2}\lambda_n(\Lambda)
}.
$$

因此，取第一列即可得到近似 SVP 解；取整组基即可得到近似 SIVP 解。

当 $\delta=3/4$ 时，$\alpha=2$，两者的近似因子为

$$
\gamma(n)=2^{(n-1)/2}.
$$

此外还有与格行列式的直接联系：

$$
\boxed{
\|b_1\|_2
\le
\alpha^{(n-1)/4}\det(\Lambda)^{1/n}
}.
$$

[2，PDF 第 2—3 页，Theorem 3]

第一项保证可以直接衔接第三篇的下界：

$$
\|b_1\|_2
\le
\alpha^{(n-1)/2}\min_i\|b_i^*\|_2
\le
\alpha^{(n-1)/2}\lambda_1(\Lambda).
$$

[1，第 3 页，Claim 1]

**多项式时间描述的是运行时间；这里保证的近似因子仍随维数指数增长。** LLL 不保证找到精确最短向量。

## 来源与阅读位置

1. 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 页运行时间分析。[原文](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf)
2. Daniele Micciancio，*Basis Reduction*，PDF 页首标注 Fall 2017，由 2019 年课程页链接。辅助阅读 §1、§3：PDF 第 2—3 页近似保证与 Theorem 3、第 6—8 页算法及势函数与比特复杂度分析。[原文](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec5.pdf)

来源于 2026-10-16 核对，正文按已确认的草稿整理。

下一篇计划：《06 Babai 最近平面算法与近似 CVP》，讨论如何利用 LLL 约化基，为给定目标寻找附近的格点。

## 引用此笔记

- [00 概览与阅读路线](/knowledge/lattices-overview/)
- [06 Babai 最近平面算法与近似 CVP](/knowledge/babai-nearest-plane/)
- [16 投影格、BKZ 与局部 SVP](/knowledge/projected-lattices-bkz-and-local-svp/)