LLL 格基约化 | Codeboy's Blog

形式陈述

给定秩 $k\ge1$ 的格基 $B=(b_1,\ldots,b_k)$ ，令 $b_i^*$ 与 $\mu_{i,j}$ 是其 Gram–Schmidt 数据：

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

对参数 $\delta\in(1/4,1)$ ，基称为 LLL-reduced，若同时满足

|\mu_{i,j}|\le\frac12\quad(j<i)

以及 Lovász 条件

\delta\|b_{i-1}^*\|^2 \le \|b_i^*\|^2+\mu_{i,i-1}^2\|b_{i-1}^*\|^2 \quad(2\le i\le k).

LLL 算法交替执行整数 size reduction 与相邻列交换；这些操作对应幺模矩阵，故输出仍生成同一格。对整数或有理输入和固定有理参数 $\delta\in(1/4,1)$ ，势函数在每次交换时按固定比例下降，可推出关于维数和输入位长度的多项式运行时间。

一个具体执行顺序是从 $i=2$ 开始，按 $j=i-1,i-2,\ldots,1$ 依次做 $b_i\leftarrow b_i-\lfloor\mu_{i,j}\rceil b_j$ ，每次更新正交化数据。然后检验第 $i$ 对的 Lovász 条件；成立则令 $i\leftarrow i+1$ ，否则交换 $b_{i-1},b_i$ 并令 $i\leftarrow\max(2,i-1)$ 。当 $i>k$ 时停止； $k=1$ 无须循环。最近整数的半整数情形采用任一固定规则即可。

环境维数为 $n$ 时，稠密实现保存基向量、正交化向量和 $\mu$ 数据需 $O(nk+k^2)$ 个整数或有理数槽；各数的位长度另行计入，槽数并非位空间界。

最常用的首向量保证是

\|b_1\| \le(\delta-1/4)^{-(k-1)/2}\lambda_1(\Lambda).

这个估计不要求先求解 SVP。令 $a=\delta-1/4>0$ ，约化条件给 $\|b_i^*\|^2\ge a\|b_{i-1}^*\|^2$ 。对任意非零格点 $v=\sum z_i b_i$ ，取最大的 $j$ 使 $z_j\ne0$ ；它在前 $j-1$ 个方向正交补中的分量为 $z_jb_j^*$ ，故

\|v\|\ge\|b_j^*\|\ge a^{(j-1)/2}\|b_1\|\ge a^{(k-1)/2}\|b_1\|.

再取最短非零 $v$ 就得到上式。取 $\delta=3/4$ 得 $\|b_1\|\le2^{(k-1)/2}\lambda_1(\Lambda)$ 。常数依赖具体的 $\delta$ 约定；不能把 $2^{(k-1)/2}$ 原样贴到任意参数。

直觉

尺寸约化和交换把两根细长偏斜基向量改成同格中更短、更接近正交的基 — LLL 的尺寸约化与基交换

size reduction 把 $b_i$ 沿较早方向的 Gram–Schmidt 系数约到最近整数，使投影系数留在 $[-1/2,1/2]$ 。Lovász 条件则阻止“真正的新方向”突然变得过短：若 $b_i^*$ 相对前一方向太小，交换两列让短结构向前移动，再重新整理系数。

算法约化的是表示，不是点集。它无法把格变得更密，也没有直接求出所有逐次极小；它保证输出基不会以无限糟糕的顺序和投影系数隐藏短向量。指数近似因子仍会随维数增长，这正是“多项式时间”与“密码参数下足够强的约化”之间的距离。

Gram–Schmidt 向量通常不是格点，只用于分析投影长度。真正输出的每个 $b_i$ 始终是原基的整数线性组合；若实现把浮点正交向量当作新列写回格基，便改变了问题。

例子与边界

下面的二维例子固定将半整数向零舍入。取

b_1=(1,1),\qquad b_2=(1,0),\qquad\delta=3/4.

有 $b_1^*=(1,1)$ 、 $\mu_{2,1}=1/2$ 、 $b_2^*=(1/2,-1/2)$ 。size-reduction 条件恰好满足，但 Lovász 两边分别为

\frac34\|b_1^*\|^2=\frac32, \qquad \|b_2^*\|^2+\frac14\|b_1^*\|^2=1,

所以必须交换。交换后先取 $(1,0)$ ，再把原 $(1,1)$ 减去它，得到 $(0,1)$ ；输出是同一个 $\mathbb Z^2$ 的正交短基。这个例子同时表明 size reduction 单独不足以约束基的顺序。

边界 $\delta\le1/4$ 不能给上述正的间隙因子， $\delta=1$ 又使经典多项式终止分析失去固定收缩余量。实际实现常取接近 $1$ 的值换取较好基，但计算开销与数值精度也随之改变。

精确算术的定理不能直接为朴素浮点实现背书。近乎相关的长基会造成 Gram–Schmidt 严重消去；可靠软件使用动态精度、整数更新与经验证的条件复查。LLL 也不是精确 SVP 算法：首向量保证是上式的维数指数近似。

推论与应用

LLL 为有理数重构、整系数多项式分解、丢番图逼近和低维格攻击提供可审计的基线。它还能作为更强 BKZ 类算法的预处理，但块约化的代价模型与近似质量不属于 LLL 定理本身。

在密码分析中，把噪声关系或模方程嵌入格后运行 LLL，只有在目标向量相对余体积与其他短向量足够突出时才可能恢复秘密。一次玩具实验成功不能推出渐近攻击；需要同时报告嵌入维数、缩放、预测根 Hermite 因子与实际资源。

参考资料

Arjen K. Lenstra, Hendrik W. Lenstra Jr., and László Lovász, “Factoring Polynomials with Rational Coefficients,” Mathematische Annalen 261, 1982, pp. 515–534。
Phong Q. Nguyen and Brigitte Vallée (eds.), The LLL Algorithm: Survey and Applications, Springer, 2010, Chs. 1–2。
Oded Regev（授课），Eyal Kaplan（记录），Lattices in Computer Science, Lecture 2: LLL Algorithm，2004，2013 年修订，§§2–3：整数操作、势函数及位复杂度。
Henri Cohen, A Course in Computational Algebraic Number Theory, Springer, 1993, Sec. 2.6。

形式陈述 ​

反向链接

形式陈述