格基约化与 LLL 算法#

前置笔记：基本区域、格行列式与正交化、基本计算格问题：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 正交化提供衡量和调整这组基所需的辅助量。

#前缀正交投影与 GSO

已经选定前 $i-1$ 列时，它们张成的空间为 $V_{i-1}=\operatorname{span}(b_1,\ldots,b_{i-1})$，约定 $V_0=\{0\}$。要比较接下来两列各自在这个空间之外增加了多少高度，可以先从它们身上扣除沿前缀的分量。

记 $\pi_i$ 为到 $V_{i-1}^{\perp}$ 的正交投影。由于 $b_1^*,\ldots,b_{i-1}^*$ 两两正交，对任意 $x\in\mathbb R^m$ 都有

下标 $i$ 表示去掉前 $i-1$ 列的方向。因此 $\pi_1$ 是恒等映射，而 $\pi_i(b_i)=b_i^*$ 正是对当前有序基做 Gram–Schmidt 正交化（GSO）得到的第 $i$ 个正交向量 [1, sec. 1]。投影用于比较长度，实际换基仍作用于原来的整数列。

#LLL 约化基的两个条件

固定参数

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

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

尺寸约化条件

这里 $\mu_{i,j}=\langle b_i,b_j^*\rangle/\|b_j^*\|_2^2$。尺寸约化要求 $b_i$ 沿每个较早正交方向 $b_j^*$ 的分量长度至多为 $\|b_j^*\|_2/2$ [1, sec. 1]。

Lovász 条件

对相邻的 $b_{k-1},b_k$，用同一个 $\pi_{k-1}$ 去掉前 $k-2$ 列的方向。Lovász 条件比较两列相对于这个共同前缀的高度 [1, sec. 1]。

若右侧严格小于左侧，改用 $b_k$ 作第 $k-1$ 列，就能把这一层的高度降到原来的 $\sqrt{\delta}$ 倍以下，算法会交换两列。$k=2$ 时，$\pi_1$ 是恒等映射，可以直接比较 $b_1,b_2$ 的长度。$k=3$ 时，$\pi_2$ 先扣除沿 $b_1$ 的分量，再比较 $b_2,b_3$ 的投影长度。

用 GSO 展开这两个投影，有

第二个投影还保留着沿 $b_{k-1}^*$ 的分量。这个分量与 $b_k^*$ 正交，由勾股定理得到等价的 Lovász 条件

再代入尺寸约化给出的 $|\mu_{k,k-1}|\le 1/2$，可得

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

#LLL 的势函数

尺寸约化条件和 Lovász 条件告诉我们，一组基何时已经约化。要说明算法一定会到达这样的状态，还需要知道它能交换多少次。每次换基都保持整格的体积，但交换两列可能改变前几列生成的子格。LLL 的势函数利用这些前缀格的体积来衡量交换取得的进展。

对 $1\le j\le n$，记 $B_j=[b_1,\ldots,b_j]$。前 $j$ 列张成的平行多面体的 $j$ 维体积平方为

定义当前有序基 $B$ 的势函数为所有前缀体积平方的乘积：

第二个等式来自计数。因子 $\|b_i^*\|_2^2$ 出现在 $D_i,D_{i+1},\ldots,D_n$ 中，共出现 $n-i+1$ 次。

对本文的满列秩整数基，每个 $B_j^TB_j$ 都是正定整数矩阵，因此每个 $D_j$ 都是正整数，$\Phi(B)\ge 1$。尺寸约化保持 $\Phi(B)$，而由 Lovász 条件失败触发的相邻交换会使它严格下降。这个下界和每次交换的下降幅度共同限制了交换次数 [1, sec. 3.1]。

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

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

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

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

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

#二维例子中的换基矩阵与势函数

取 $b_1=(2,1)^T$、$b_2=(3,2)^T$，按列组成初始基，令 $\delta=3/4$。记 $E_t$ 为第 $t$ 步的换基矩阵，$U_t$ 为从初始基到第 $t$ 步的累计换基矩阵。每次列操作都对应右乘，因此

二维基 $B=[b_1,b_2]$ 只有两个前缀。第一列给出 $D_1=\|b_1\|_2^2$，整组基给出 $D_2=\det(B^TB)=(\det B)^2$。代入定义可得

本例中 $\det B^{(0)}=1$，每次幺模换基都保持 $|\det B|=1$，所以每一步的势函数就是当前第一列的长度平方。初始值为 $\Phi(B^{(0)})=2^2+1^2=5$。

在原始直角坐标系中固定当前第一列 $a=b_1$，用 $p=(x,y)^T$ 表示第二列的候选端点。因为 $\pi_1$ 是恒等映射，两项约化条件在这个平面上分别为

尺寸约化的两条边界是与 $a$ 垂直的平行线 $\langle p,a\rangle=\pm\|a\|_2^2/2$。Lovász 条件的边界是以原点为圆心、半径为 $\sqrt{\delta}\|a\|_2$ 的圆。图中浅色阴影取平行线之间且在圆周上或圆外的部分，表示两个条件同时成立的端点位置。算法通过整数换基选取实际端点。

查看 Typst 源码

#import "../../.typst/cinderfolio.typ": cf-palette
#import "@preview/cetz:0.5.2"
#let cf = cf-palette(mode: "dark")
#set page(width: auto, height: auto, margin: 10pt, fill: cf.background)
#set text(size: 9pt, fill: cf.foreground)

#let lll-delta = 3 / 4
#let first = cf.series.at(3)
#let second = cf.series.at(5)
#let boundary = cf.series.at(0)
#let shade = color.mix((boundary, 18%), cf.background)

#let panel(title, a, b, coefficient, size-ok, lovasz-ok, phi, old: none) = [
  #text(weight: "bold", size: 11pt, title)
  #v(3pt)
  $b_1 = (#a.at(0), #a.at(1)), quad b_2 = (#b.at(0), #b.at(1))$
  #v(4pt)
  #cetz.canvas(length: 0.8cm, {
    import cetz.draw: *
    let n = calc.sqrt(a.at(0) * a.at(0) + a.at(1) * a.at(1))
    let half = n / 2
    let radius = calc.sqrt(lll-delta) * n
    // p = s * a/|a| + t * perpendicular(a)/|a|.
    // The strip is |s| <= |a|/2; outside the circle, s^2+t^2 >= delta*|a|^2.
    let xy(s, t) = ((s * a.at(0) - t * a.at(1)) / n, (s * a.at(1) + t * a.at(0)) / n)
    for side in (-1, 1) {
      let arc-points = range(33).map(i => {
        let s = -half + n * i / 32
        xy(s, side * calc.sqrt(radius * radius - s * s))
      })
      let edge-y = if side * a.at(0) > 0 { 2.5 } else { -2.5 }
      let cap(s) = xy(s, (edge-y * n - s * a.at(1)) / a.at(0))
      line(..arc-points, cap(half), cap(-half), close: true, fill: shade, stroke: none)
    }
    for x in range(-2, 4) {
      line((x, -2.5), (x, 2.5), stroke: (paint: cf.border, thickness: 0.3pt))
    }
    for y in range(-2, 3) {
      line((-2.7, y), (3.4, y), stroke: (paint: cf.border, thickness: 0.3pt))
    }
    for s in (-half, half) {
      line(xy(s, (-2.5 * n - s * a.at(1)) / a.at(0)),
        xy(s, (2.5 * n - s * a.at(1)) / a.at(0)),
        stroke: (paint: boundary, thickness: 0.8pt, dash: "dashed"))
    }
    circle((0, 0), radius: radius, stroke: (paint: cf.diagram-stroke, thickness: 0.9pt))
    line((-2.7, 0), (3.5, 0), stroke: cf.text-muted, mark: (end: ">"))
    line((0, -2.5), (0, 2.6), stroke: cf.text-muted, mark: (end: ">"))
    content((3.55, -0.18), $x$)
    content((0.18, 2.6), $y$)
    for tick in (-2, 2) {
      content((tick, -2.7), text(fill: cf.text-muted, size: 7pt)[#tick])
      content((-2.95, tick), text(fill: cf.text-muted, size: 7pt)[#tick])
    }
    if old != none {
      line(old, b, stroke: (paint: cf.text-muted, dash: "dashed"), mark: (end: ">"))
      circle(old, radius: 0.07, fill: cf.background, stroke: cf.text-muted)
    }
    line((0, 0), a, stroke: (paint: first, thickness: 1.6pt), mark: (end: ">"))
    line((0, 0), b, stroke: (paint: second, thickness: 1.6pt), mark: (end: ">"))
    content((a.at(0) + 0.18, a.at(1) - 0.2), text(fill: first)[$b_1$])
    content((b.at(0) + 0.18, b.at(1) + 0.25), text(fill: second)[$b_2$])
    circle((0, 0), radius: 0.035, fill: cf.foreground, stroke: none)
  })
  #v(3pt)
  $mu = #coefficient, quad Phi = #phi$ #linebreak()
  Size: #size-ok #h(6pt) Lovasz: #lovasz-ok
]

#text(size: 15pt, weight: "bold")[LLL reduction in fixed Cartesian coordinates]
#v(4pt)
$delta = 3/4$. Shading: both conditions hold. Open dots: previous $b_2$.
#v(10pt)
#grid(columns: (auto, auto), column-gutter: 18pt, row-gutter: 15pt,
  panel("0. Initial basis", (2, 1), (3, 2), $8/5$, "no", "OK", 5),
  panel("1. Size reduction", (2, 1), (-1, 0), $-2/5$, "OK", "no", 5, old: (3, 2)),
  panel("2. Swap columns", (-1, 0), (2, 1), $-2$, "no", "OK", 1),
  panel("3. Size reduction", (-1, 0), (0, 1), $0$, "OK", "OK", 1, old: (2, 1)),
)
#v(8pt)
Size: $abs(p dot b_1) <= norm(b_1)^2/2$;
Lovasz: $norm(p)^2 >= delta norm(b_1)^2$.

四格共用同一原点、坐标轴和刻度。两种分类色的箭头分别表示当前 $b_1$ 与 $b_2$，标签与箭头同色；条带边界使用虚线，Lovász 圆使用实线。空心点标出尺寸约化前的 $b_2$ 端点，灰色虚线表示它的移动。每格下方的 Size 和 Lovasz 分别标明两项条件是否成立，OK 表示成立，no 表示不成立。

#第一步　对第二列做尺寸约化

初始投影系数为 $\mu_{2,1}=(2\cdot3+1\cdot2)/5=8/5$，最近整数为 $2$。令 $b_2\leftarrow b_2-2b_1=(-1,0)^T$。新第二列在旧基下的系数是 $(-2,1)^T$，这正是 $E_1$ 的第二列。

从图 0 到图 1，第二列端点沿 $-2b_1$ 从 $(3,2)^T$ 移到 $(-1,0)^T$。此时 $\mu_{2,1}$ 从 $8/5$ 变为 $-2/5$，端点进入尺寸约化的条带，但落在 Lovász 圆内。第一列仍是 $(2,1)^T$，所以 $\Phi(B^{(1)})=5$。

#第二步　检查 Lovász 条件并交换两列

在二维，Lovász 条件右侧是 $\|b_2^*\|_2^2+\mu_{2,1}^2\|b_1\|_2^2=\|b_2\|_2^2$。代入第一步得到的两列，有

条件失败，交换两列。

对照图 1 和图 2，两支箭头的端点位置相同，但第一列从 $(2,1)^T$ 换成了 $(-1,0)^T$。因此条带边界从 $2x+y=\pm5/2$ 转为 $x=\pm1/2$，圆的半径平方也从 $15/4$ 变为 $3/4$。新的第二列 $(2,1)^T$ 落在竖直条带外，因此还需要一次尺寸约化。

交换使势函数从 $5$ 降到 $1$。这一次的下降比例恰好是交换前两列长度平方之比，即 $\Phi(B^{(2)})/\Phi(B^{(1)})=1/5<\delta$。

#第三步　对交换后的第二列做尺寸约化

交换后 $b_1=(-1,0)^T$、$b_2=(2,1)^T$。虽然势函数已经降到 $1$，当前投影系数仍是 $\mu_{2,1}=-2$。取最近整数 $q=-2$，令 $b_2\leftarrow b_2-qb_1=b_2+2b_1=(0,1)^T$。

图 3 中，第二列端点移到 $(0,1)^T$，落入浅色阴影。第一列仍是 $(-1,0)^T$，所以 $\Phi(B^{(3)})=1$。最终两列正交且长度均为 $1$，尺寸约化条件为 $|\mu_{2,1}|=0\le 1/2$，Lovász 条件为 $3/4\le 1$。又因 $B^{(3)}=B^{(0)}U_3$ 且 $U_3$ 是行列式为 $-1$ 的整数矩阵，输出是原格 $\mathbb Z^2$ 的一组 $3/4$-LLL 约化基。

#LLL 在多项式时间内完成格基约化

尺寸约化 $b_i\leftarrow b_i-qb_j$（$j<i$，$q\in\mathbb Z$）保持每个前缀格，因此所有 $D_j$ 和它们的乘积 $\Phi(B)$ 都保持不变。

现在设第 $k$ 处的 Lovász 条件失败，算法交换 $b_{k-1}$ 与 $b_k$，得到 $B'$。这次交换只可能改变 $D_{k-1}$。更短的前缀不含这两列，更长的前缀同时包含两列，交换次序保持它们的体积。

第 $k-1$ 个前缀的底面由前 $k-2$ 列确定。交换前后，底面相同，两次的高分别是 $\|\pi_{k-1}(b_{k-1})\|_2$ 和 $\|\pi_{k-1}(b_k)\|_2$。由于 $D_{k-1}$ 是体积平方，势函数之比就是这两个高度的平方之比 [1, sec. 3.1]。

最后一个不等号正是触发交换的 Lovász 判据。图 1 中，$b_2$ 落在圆内，对应的平方长度之比为 $1/5<3/4$。这也是图 1 到图 2 势函数从 $5$ 降到 $1$ 的原因。

从输入基 $B_{\mathrm{in}}$ 开始，若已经交换 $s$ 次，当前势函数至多为 $\delta^s\Phi(B_{\mathrm{in}})$，同时又至少为 $1$。于是

伪代码的每轮要么返回，要么执行一次交换，因此算法必定终止。若输入列的最大范数为 $A$，Hadamard 不等式给出初始 $D_j\le A^{2j}$，从而 $\log\Phi(B_{\mathrm{in}})\le n(n+1)\log A$。对固定的 $\delta<1$，这就给出了交换次数的多项式上界。再控制中间整数和正交化系数的分子、分母位长，即可得到总运行时间的多项式界 [1, secs. 3.1–3.2]。

#LLL 给出首向量和整组基的长度上界

令

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

以及

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

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

此外，首个基向量的长度还满足下式给出的格行列式上界 [1, pp. 2–3]。

记 $g_i=\|b_i^*\|_2$。任意非零格向量的最后一个非零整数系数若为 $z_k$，该向量在前 $k-1$ 列正交补上的投影就是 $z_kb_k^*$，因此 $\lambda_1(\Lambda)\ge\min_i g_i$。另一方面，LLL 条件给出 $g_i\le\sqrt{\alpha}\,g_{i+1}$。把这个相邻长度界至多连乘 $n-1$ 次，得到

中间的上界可以从本次输出的 GSO 长度直接算出。最右侧的上界只依赖维数和约化参数，对每一组输出都成立 [1, sec. 1]。例如，前面二维例子的最终基满足 $g_1=g_2=1$，所以实际近似因子恰好是 $1$，而 $\delta=3/4$ 时的通用上界是 $\sqrt 2$。

指数级差距也可以实际发生。取 $\delta=3/4$，先看正交基 $B=\operatorname{diag}(100,90,81)$。后一列总是前一列长度的 $0.9$ 倍，而触发交换要求这个比例小于 $\sqrt{3/4}\approx0.866$。所以 LLL 接受这个顺序，返回的首向量长 $100$，格的最短向量长 $81$。推广到 $n$ 维，取 $b_i=10^{n-i}9^{i-1}e_i$，其中 $e_i$ 是第 $i$ 个坐标单位向量。每一对相邻列都通过检查，实际近似因子却是 $(10/9)^{n-1}$。这个例子说明，逐对允许的小幅下降可以累积成指数级差距，而具体输入能接近通用上界多少，还取决于它的基。

#阅读位置

• LLL 通过尺寸约化与基向量交换得到满足约化条件的格基，并具有多项式运行时间 [2, pp. 2–8]。
• LLL 的近似保证可由正交分量的长度关系推出，复杂度分析还需控制势函数变化与操作数的比特长度 [1, pp. 2–3, 6–8]。

接下来阅读Babai 最近平面算法与近似 CVP，讨论如何利用 LLL 约化基，为给定目标寻找附近的格点。

#参考文献