> 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.

# 浮点 LLL 的精度与正确性

在[格基约化与 LLL 算法](https://shijin.space/knowledge/lattice-reduction-and-lll/index.md)的二维例子中，第一步算出 $\mu_{2,1}=8/5$，取最近整数 $q=2$，把第二列更新为 $b_2-2b_1$。这一步可以分开执行：用浮点数估计 $\mu_{2,1}$，选定整数 $q$，再用精确整数运算更新基。

这种分工有一个重要后果。即使 $q$ 选错，减去整数倍的另一列仍是幺模换基，输出仍生成原格。但更新后的投影系数是 $\mu_{2,1}-q$，它可能落在 $[-1/2,1/2]$ 之外。**保持原格取决于怎样执行换基，达到约化条件还取决于怎样选择换基。**

## 取整和交换各有一条判定边界

先沿用上一篇的严格尺寸条件 $|\mu_{i,j}|\le 1/2$。尺寸约化要判断 $\mu_{i,j}$ 最接近哪个整数，相邻两个选择的分界在半整数处。例如 $8/5=1.6$ 距离最近的分界 $1.5$ 有 $0.1$。只要近似值的绝对误差严格小于 $0.1$，这一步仍会取到 $q=2$。

交换则取决于另一个量。沿用前缀正交投影 $\pi_{k-1}$，记 $g_i=\|b_i^*\|_2$。将 Lovász 条件的右侧减去左侧，定义

$$
\begin{aligned}
\Delta_k
&=\|\pi_{k-1}(b_k)\|_2^2-\delta\|\pi_{k-1}(b_{k-1})\|_2^2\\
&=g_k^2+\mu_{k,k-1}^2g_{k-1}^2-\delta g_{k-1}^2.
\end{aligned}
$$

当 $\Delta_k<0$ 时交换，当 $\Delta_k\ge 0$ 时通过检查。上一篇图 1 中，$\pi_1$ 是恒等映射，尺寸约化后的两列是 $(2,1)^T$ 和 $(-1,0)^T$，所以 $\Delta_2=1-15/4=-11/4$。端点落在圆内，差值为负，两种表述给出同一个决定。

这个符号也关系到终止性。若交换相邻两列，上一篇的势函数公式给出

$$
\frac{\Phi(B')}{\Phi(B)}
=\frac{\|\pi_{k-1}(b_k)\|_2^2}{g_{k-1}^2}
=\delta+\frac{\Delta_k}{g_{k-1}^2}.
$$

因此，真实的 $\Delta_k<0$ 才保证这次交换把势函数降到原来的 $\delta$ 倍以下。错过一次应做的交换，可能让程序过早接受当前基。做了一次不满足该判据的交换，则失去了精确 LLL 证明所用的下降保证 \[[1, sec. 3.1](https://shijin.space/knowledge/floating-point-lll/index.md#ref-floating-point-lll-Micciancio2017BasisReduction)\]。

## 在同一张平面图上制造两次误判

固定第一列 $b_1=(1000,0)^T$，令第二列为 $p=(x,y)^T$，仍取 $\delta=3/4$。这时 $\mu_{2,1}=x/1000$，尺寸约化条带的边界是 $x=\pm500$，Lovász 圆的半径平方是 $750000$。下面有意将判定量先四舍五入到两位小数，再作决定，以便直接看见误差的影响。

**在条带边缘。** 取 $p=(499,1)^T$ 或 $p=(501,1)^T$，精确投影系数分别为 $0.499$ 和 $0.501$。前者应取 $q=0$，后者应取 $q=1$。两者舍入后都变成 $0.50$。若统一取 $q=0$，第二个输入的系数仍是 $0.501$。若统一取 $q=1$，第一个输入的系数变成 $-0.501$。无论怎样处理这个表面上的平局，总有一个输入未完成严格尺寸约化，而两次整数操作都保持原格。

**在圆周附近。** 取 $p=(0,866)^T$，它已经在条带内。检查平方长度之比，有

$$
\frac{\|p\|_2^2}{\|b_1\|_2^2}
=\frac{866^2}{1000^2}
=0.749956<0.75.
$$

端点在圆内，应当交换。若先将比值舍入为 $0.75$，程序就会按等号接受当前基。这个例子说明，判定需要的精度取决于**真实值离边界有多远**。

## 为什么不大的整数也会丢失投影高度

工作精度指浮点数保留的有效位数。把整组基乘同一个 $2^k$，整数条目会变长，但 $\mu_{i,j}$ 和 Lovász 判据中的长度比保持不变。反过来，两列几乎平行时，即使整数条目不大，第二列在第一列正交补上的高度也可能很小。

取整数 $N\ge 2$，令 $b_1=(N,1)^T$、$b_2=(N+1,1)^T$。两列围成的平行四边形面积为 $1$。以第一列为底，第二个正交高度的平方为

$$
s=g_2^2=\frac{1}{N^2+1}.
$$

记 $G=B^TB$。若从 Gram 矩阵计算同一个量，先算 $T=G_{12}^2/G_{11}$，再算 $s=G_{22}-T$。这里

$$
G_{11}=N^2+1,\qquad G_{12}=N(N+1)+1,\qquad G_{22}=(N+1)^2+1.
$$

相减的两项都是 $N^2$ 量级，留下的差只有 $N^{-2}$ 量级。究竟会损失多少位，可以沿着这两步运算计算。

设二进制有效精度为 $w$ 位（含首位），采用就近舍入，单位舍入误差为 $u=2^{-w}$。先假定三个 Gram 元素均已精确读入，运算无上溢或下溢。在这个模型中，每次乘法、除法或减法的计算结果可写成精确结果乘以 $1+e$，其中 $|e|\le u$ \[[2, sec. 2](https://shijin.space/knowledge/floating-point-lll/index.md#ref-floating-point-lll-NguyenStehle2009L2)\]。计算 $T$ 要做一次乘法和一次除法，所以

$$
\widehat T=T(1+\theta),\qquad |\theta|\le (1+u)^2-1=2u+u^2.
$$

于是最后一次相减在舍入前已经变成 $G_{22}-\widehat T=s-T\theta$。再计入这次减法自身的舍入，得到

$$
\frac{|\widehat s-s|}{s}
\le u+(1+u)(2u+u^2)\frac{T}{s}.
$$

关键是式中的 $T/s$。本例恰有 $s=1/G_{11}$，所以 $T/s=G_{12}^2$，随 $N$ 按 $N^4$ 的量级增长。乘除步骤带来的绝对误差至多为 $O(uN^2)$，换算成小差值 $s$ 的相对误差，上界就成为 **$O(uN^4)$**。要由这个界保证相对误差至多为 $2^{-t}$，取 $w=4\log_2 N+t+O(1)$ 位足够，其中加法常数取足。对这条求值公式，$N$ 每翻一倍，维持同一误差保证大约多需 4 位。这是充分精度的估计，具体输入的舍入误差可以更小。

```python
from fractions import Fraction

N = 2**14
g11 = N*N + 1
g12 = N*(N + 1) + 1
g22 = (N + 1)**2 + 1

exact = g22 - Fraction(g12*g12, g11)
a, b, c = map(float, (g11, g12, g22))
term = b*b/a
print(exact, term == c, c - term)  # 1/268435457 True 0.0
```

双精度有 $53$ 位有效精度。此时 $uN^4=8$，上述界已经无法保证小的相对误差。三个 Gram 元素本身都能精确表示，但乘除所得的 `term` 已经舍入到与 `c` 相同的浮点数。最后的减法准确地返回了零，而真实的 $s>0$，实际相对误差为 $1$。如果改在整数上先求 $G_{11}G_{22}-G_{12}^2=1$，再除以 $G_{11}$，两大数抵消时那一个单位的差就保留下来了。

## L² 与 H-LLL 怎样保证输出

**L² 保留精确的 Gram 矩阵。** Nguyen 和 Stehlé 随整数换基更新 $G=B^TB$，从精确内积出发，用浮点 Cholesky 型递推得到 GSO 近似。处理当前列时，可以先减去一组较早列的整数倍，再依据更新后的精确数据重算近似系数，逐次完成尺寸约化。这样，大系数的整数部分可以分几次消去 \[[2, secs. 3.2–3.3](https://shijin.space/knowledge/floating-point-lll/index.md#ref-floating-point-lll-NguyenStehle2009L2)\]。

其保证有明确的参数范围。固定 $1/4<\delta<1$ 和 $1/2<\eta<\sqrt{\delta}$，在论文的算术模型中，选择随格秩线性增长的足够工作精度，L² 会在多项式时间内输出满足 Lovász 条件及 $|\mu_{i,j}|\le\eta$ 的基。这里 $\eta-1/2$ 给浮点判定留出了余量。例如，$0.501$ 满足 $\eta=0.51$ 的尺寸界，却超出了上一篇的严格尺寸界。沿用上一篇的长度推导时，相邻高度界也相应变为 $g_k^2\ge(\delta-\eta^2)g_{k-1}^2$ \[[2, secs. 2.2, 3.4](https://shijin.space/knowledge/floating-point-lll/index.md#ref-floating-point-lll-NguyenStehle2009L2)\]。

**H-LLL 直接对基做 Householder QR。** 写 $B=QR$，取 $R$ 的对角元为正，则 $R_{jj}=g_j$，且对 $j<i$ 有 $R_{ji}=g_j\mu_{i,j}$。算法用 Householder 反射计算 $R$ 的近似，再对原整数基执行列操作。其误差分析允许非对角元的误差还与当前列的尺度有关，论文相应采用弱尺寸条件

$$
|R_{ji}|\le\eta R_{jj}+\theta R_{ii},\qquad j<i.
$$

在论文规定的参数与精度下，算法输出满足这条弱尺寸条件和 Lovász 条件的原格基。比较两种算法的输出时，要连同 $\eta$、$\theta$ 和所检验的不等式一起比较 \[[3, secs. 2, 4](https://shijin.space/knowledge/floating-point-lll/index.md#ref-floating-point-lll-MorelStehleVillard2009HLLL)\]。

## 什么时候提高精度，怎样检查结果

对小规模实现，可以把“这一步能否相信”写成区间判断。假设已有可靠的误差上界，能够保证真实值落在所算区间内。

- **取整。** 若 $\mu_{i,j}$ 的整个区间落在 $(q-1/2,q+1/2)$ 内，就采用整数 $q$。若区间碰到半整数边界，就提高精度或用精确分数复核。真实值恰为半整数时，按约定选择任一最近整数。
- **交换。** 若 $\Delta_k$ 区间的上端点小于 $0$，就交换。若下端点大于等于 $0$，就接受。其余情况应重算。恰好等于 $0$ 时，精确 Lovász 条件成立。

最后把两个问题分别验算。先用精确整数检查 $U\in\mathbb Z^{n\times n}$、$|\det U|=1$ 和 $B_{\rm out}=B_{\rm in}U$，验证输出生成原格。再从 $B_{\rm out}$ 独立重算 GSO，按任务要求检查全部尺寸条件和每个相邻位置的 Lovász 条件。若要求上一篇的严格 LLL，就用 $1/2$ 作为尺寸阈值。这样即使浮点程序走出了与手算不同的换基路径，也能直接判断它交出的基是否合格。

## 参考文献 {#references-floating-point-lll}

<div id="refs-floating-point-lll" class="references csl-bib-body">

<div id="ref-floating-point-lll-Micciancio2017BasisReduction" class="csl-entry">

1\. Daniele Micciancio. *Basis reduction*. 2017. [原文](https://cseweb.ucsd.edu/classes/fa19/cse206A-a/lec5.pdf).

</div>

<div id="ref-floating-point-lll-NguyenStehle2009L2" class="csl-entry">

2\. Phong Q. Nguyen and Damien Stehlé. *An LLL algorithm with quadratic complexity*. SIAM Journal on Computing. 2009. [DOI](https://doi.org/10.1137/070705702).

</div>

<div id="ref-floating-point-lll-MorelStehleVillard2009HLLL" class="csl-entry">

3\. Ivan Morel, Damien Stehlé, and Gilles Villard. *H-LLL: Using Householder inside LLL*. Proceedings of the 2009 international symposium on symbolic and algebraic computation. 2009. [DOI](https://doi.org/10.1145/1576702.1576740).

</div>

</div>