LLL 格基约化

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

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

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

在二维取

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

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

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

精确算术的定理不能直接为朴素浮点实现背书。近乎相关的长基会造成 Gram–Schmidt 严重消去；可靠软件使用动态精度、整数更新与经验证的条件复查。LLL 也不是精确 SVP公理库最短向量问题Shortest vector problem · SVP · 格最短向量问题从格基寻找达到或近似第一个逐次极小的非零格向量。 算法：首向量保证是上式的维数指数近似。

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

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