For AI agents: the complete documentation index is available at https://shijin.space/llms.txt, the full documentation bundle is available at https://shijin.space/llms-full.txt, and this page is available as Markdown at https://shijin.space/knowledge/lattice-reduction-and-lll/index.md.
ShiJin

    05 格基约化与 LLL 算法

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

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

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

    bi=bi∗+∑j<iμi,jbj∗.b_i=b_i^*+\sum_{j<i}\mu_{i,j}b_j^*.

    格基约化的目标

    格基约化通过幺模变换

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

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

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

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

    LLL 约化基的两个条件

    固定参数

    14<δ<1,\frac14<\delta<1,

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

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

    尺寸约化条件

    ∣μi,j∣≤12,j<i.\boxed{ |\mu_{i,j}|\le\frac12,\qquad j<i }.

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

    Lovász 条件

    δ∥bk−1∗∥22≤∥bk∗∥22+μk,k−12∥bk−1∗∥22,2≤k≤n.\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 }.

    结合尺寸约化条件可得

    ∥bk∗∥22≥(δ−14)∥bk−1∗∥22.\|b_k^*\|_2^2 \ge \left(\delta-\frac14\right)\|b_{k-1}^*\|_2^2.

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

    ∥bk∗∥22≥12∥bk−1∗∥22.\|b_k^*\|_2^2\ge\frac12\|b_{k-1}^*\|_2^2.

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

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

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

    q=round⁡(μi,j),bi←bi−qbj.q=\operatorname{round}(\mu_{i,j}), \qquad b_i\leftarrow b_i-qb_j.

    这里减去的是整数倍的基向量 bjb_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_k

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

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

    一个简短例子

    取

    b1=(2,1),b2=(3,2),δ=34.b_1=(2,1),\qquad b_2=(3,2),\qquad \delta=\frac34.

    原基行列式为 11，生成 Z2\mathbb Z^2。

    首先，

    μ2,1=85,b2←b2−2b1=(−1,0).\mu_{2,1}=\frac{8}{5}, \qquad b_2\leftarrow b_2-2b_1=(-1,0).

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

    34∥b1∥22=154>1=∥b2∥22,\frac34\|b_1\|_2^2=\frac{15}{4}>1=\|b_2\|_2^2,

    因此交换两个向量，得到

    b1=(−1,0),b2=(2,1).b_1=(-1,0),\qquad b_2=(2,1).

    再做一次尺寸约化：

    b2←b2+2b1=(0,1).b_2\leftarrow b_2+2b_1=(0,1).

    最终得到基 (−1,0),(0,1)(-1,0),(0,1)，满足两项约化条件，生成的格仍为 Z2\mathbb Z^2。

    为什么能够终止，并在多项式时间内完成

    记前 kk 个基向量构成的矩阵为 Bk=[b1,…,bk]B_k=[b_1,\ldots,b_k]，定义势函数

    Φ(B)=∏k=1ndet⁡(BkTBk)=∏i=1n∥bi∗∥2 2(n−i+1).\Phi(B) = \prod_{k=1}^{n}\det(B_k^TB_k) = \prod_{i=1}^{n}\|b_i^*\|_2^{\,2(n-i+1)}.

    整数基的每个 Gram 行列式都是正整数，所以 Φ(B)≥1\Phi(B)\ge1。

    • 尺寸约化保持 Φ(B)\Phi(B) 不变。
    • 每次因违反 Lovász 条件而交换，都有 Φ(Bnew)<δ Φ(Bold)\Phi(B_{\mathrm{new}})<\delta\,\Phi(B_{\mathrm{old}})。

    因此交换次数有限。对固定 δ<1\delta<1，初始 log⁡Φ(B)\log\Phi(B) 受输入比特长度的多项式控制；再结合中间数值比特长度的界，可得 LLL 的总运行时间为输入长度的多项式。

    这里需要同时控制操作次数和操作数的比特长度。[2，PDF 第 6—8 页，§3.1—§3.2]

    LLL 提供什么保证

    令

    α=1δ−14.\alpha=\frac{1}{\delta-\frac14}.

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

    ∥b1∥2≤α(n−1)/2λ1(Λ),\boxed{ \|b_1\|_2 \le \alpha^{(n-1)/2}\lambda_1(\Lambda) },

    以及

    max⁡i∥bi∥2≤α(n−1)/2λn(Λ).\boxed{ \max_i\|b_i\|_2 \le \alpha^{(n-1)/2}\lambda_n(\Lambda) }.

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

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

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

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

    ∥b1∥2≤α(n−1)/4det⁡(Λ)1/n.\boxed{ \|b_1\|_2 \le \alpha^{(n-1)/4}\det(\Lambda)^{1/n} }.

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

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

    ∥b1∥2≤α(n−1)/2min⁡i∥bi∗∥2≤α(n−1)/2λ1(Λ).\|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 页运行时间分析。原文
    2. Daniele Micciancio，Basis Reduction，PDF 页首标注 Fall 2017，由 2019 年课程页链接。辅助阅读 §1、§3：PDF 第 2—3 页近似保证与 Theorem 3、第 6—8 页算法及势函数与比特复杂度分析。原文

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

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

    引用此笔记