格基约化算法

格基约化（LLL）算法把格（几何数论）的给定基变换成"几乎正交且短"的基，是高维格中求短向量、解近似最近向量问题（CVP）的核心工具，把Minkowski凸体定理等存在性结论变成可执行的算法。

问题

给定秩 $n$ 的格 $L$ 与一组基 $b_1,\dots,b_n$，求较短的非零格向量。最短向量问题（SVP）在高维是 NP-困难的，但 LLL 在多项式时间内给出近似因子 $2^{(n-1)/2}$ 的解。

LLL 约化条件

设 $\{b_i^*\}$ 为 Gram–Schmidt 正交化，$\mu_{i,j}=\dfrac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}$。基称为 $\delta$-LLL 约化的（通常 $\delta=3/4$），若满足：

1. 尺寸约化：$|\mu_{i,j}|\le\dfrac12$（$j<i$）
2. Lovász 条件：$\delta\|b_i^*\|^2\le\|b_{i+1}^*+\mu_{i+1,i}b_i^*\|^2$

性质

• 第一向量满足 $\|b_1\|\le2^{(n-1)/2}\lambda_1$ 与 $\|b_1\|\le2^{(n-1)/4}(\det L)^{1/n}$（$\lambda_1$ 为最短非零向量长度）
• 算法多项式时间：$O(n^4\log B)$ 次位运算（$B$ 为基向量长度的对数上界）

示例

约化 $\mathbb{Z}^2$ 中由 $b_1=(1,2)$、$b_2=(3,4)$ 张成的格：$\mu_{2,1}=\dfrac{1\cdot3+2\cdot4}{1^2+2^2}=\dfrac{11}{5}$，四舍五入取 $2$，得 $b_2\gets b_2-2b_1=(1,0)$；因 $\|b_2\|^2=1<5=\|b_1\|^2$ 交换，再减 $1$ 倍得 $b_2=(0,2)$。最终基 $\{(1,0),(0,2)\}$ 正交、满足 LLL 条件，最短向量为 $(1,0)$（长度 $1$），$\det L=2$。

应用

• 联立丢番图逼近、整数多项式分解、子集和（背包）密码的破解
• 格基密码（NTRU、基于格的签名等）的安全性分析与构造基础，是后量子密码的主要候选方向
• 可视为狄利克雷逼近定理的高维算法实现