LLL 与 BKZ 算法：理论、实现与优化

推论 2.1 格的体积（行列式）与基的选择无关。

证明：

格的体积定义为基矩阵的 Gram 行列式的平方根：

$$ \det(L) = \sqrt{\det(B^T B)} $$

若 $C = BU$，其中 $U$ 是幺模矩阵，则：

$$ \det(C^T C) = \det(U^T B^T B U) = \det(U^T)\det(B^T B)\det(U) = \det(B^T B) $$

因此，$\det(L)$ 与基的选择无关。

子格与投影格

定义 2.2 设 $L$ 是 $\mathbb{R}^n$ 中的格，$M$ 是 $L$ 的非空子集，若 $M$ 本身也是一个格，则称 $M$ 是 $L$ 的子格。

定义 2.3 设 $L$ 是 $\mathbb{R}^n$ 中的格，$\pi$ 是从 $\mathbb{R}^n$ 到某个子空间 $V$ 的正交投影，则 $\pi(L)$ 称为 $L$ 在 $V$ 上的投影格。

投影格在 BKZ 算法中具有重要作用，用于将高维格问题转化为低维子格问题进行处理。

2.2 Gram-Schmidt（GS）正交化

完整推导公式与几何意义

Gram-Schmidt 正交化是格基约减的基础工具，用于将任意格基转化为正交基。

算法 2.1 Gram-Schmidt 正交化

输入：格基 B = [b₁, b₂, ..., b_d]
输出：正交基 B* = [b₁*, b₂*, ..., b_d*] 和系数矩阵 μ
1. 初始化 b₁* = b₁
2. 对于 i = 2 到 d：
   a. b_i* = b_i
   b. 对于 j = 1 到 i-1：
      i. μ_ij = ⟨b_i, b_j*⟩ / ⟨b_j*, b_j*⟩
      ii. b_i* = b_i* - μ_ij * b_j*
3. 返回 B* 和 μ

几何意义：

• $b_i^*$ 是 $b_i$ 在 $span(b_1, b_2, \ldots, b_{i-1})^\perp$（即与前 i-1 个向量正交的子空间）上的投影。
• $\mu_{ij}$ 表示 $b_i$ 在 $b_j^*$ 方向上的分量系数。

浮点误差累积的影响与控制

在实际计算中，Gram-Schmidt 正交化会受到浮点运算误差的影响。误差主要来源于两个方面：

1. 浮点数的有限精度表示
2. 除法运算引入的舍入误差

定理 2.2（误差上界）设 $\hat{B}^$ 是浮点计算得到的 Gram-Schmidt 正交基，$B^$ 是精确结果，则存在常数 $C$，使得：

$$ |\hat{B}^* - B^*| \leq C \cdot \epsilon \cdot |B|^2 $$

其中 $\epsilon$ 是机器精度，$|B|$ 是基矩阵的谱范数。

为了控制误差累积，实际实现中通常采用以下策略：

1. 使用更高精度的浮点数（如双精度或扩展精度）
2. 定期重新正交化
3. 在 BKZ 算法中，块处理时重新计算投影，减少误差传播

2.3 关键常数与不等式

Hermite 常数

定义 2.4 Hermite 常数 $\gamma_d$ 定义为：

$$ \gamma_d = \inf \left{ \gamma > 0 \mid \text{对于所有 } d \text{维格 } L, \exists \ \mathbf{v} \in L \setminus {0} \text{使得} \ |\mathbf{v}|^2 \leq \gamma \cdot \det(L)^{2/d} \right} $$

Hermite 常数的上界与格基约减算法的性能密切相关。对于 LLL 算法，有以下结果：

定理 2.3（LLL 与 Hermite 常数）设 $B$ 是 LLL 约减基，则：

$$ |\mathbf{b}_1|^2 \leq 2^{d-1} \cdot \det(L)^{2/d} $$

即 $\gamma_d \leq 2^{d-1}$，但这是一个非常宽松的上界。

Mordell 不等式

Mordell 不等式是 BKZ 算法的理论基础，它将局部格基约减与全局约减质量联系起来。

定理 2.4（Mordell 不等式）设 $L$ 是 $d$ 维格，$k$ 是正整数，$1 \leq k \leq d$，则：

$$ \lambda_k(L) \leq \left( \prod_{i=1}^k \gamma_i \right)^{1/2} \cdot \det(L)^{1/d} $$

其中 $\lambda_k(L)$ 是格 $L$ 的第 $k$ 个连续极小。

BKZ 算法通过对大小为 $\beta$ 的块进行局部约减，使得全局约减质量满足：

$$ |\mathbf{b}1|^2 \leq \left( \prod{i=1}^\beta \gamma_i \right)^{1/2} \cdot \det(L)^{2/d} $$

当 $\beta$ 增大时，这个上界会显著改善。

Rankin 常数与 HKZ 约减

定义 2.5 Rankin 常数 $\rho_d$ 定义为：

$$ \rho_d = \inf \left{ \rho > 0 \mid \text{对于所有 } d \text{维格 } L, \exists \ \text{线性无关向量 } \mathbf{v}_1, \ldots, \mathbf{v}_d \in L \right. $$

$$ \left. \text{使得} \ \prod_{i=1}^d |\mathbf{v}_i|^2 \leq \rho \cdot \det(L)^2 \right} $$

HKZ（Hermite-Korkine-Zolotarev）约减是一种理想的格基约减，它产生的基满足：

$$ |\mathbf{b}_i^*| = \lambda_i(L_i) $$

其中 $L_i$ 是 $L$ 在 $span(\mathbf{b}1, \ldots, \mathbf{b}{i-1})^\perp$ 上的投影格。HKZ 约减的计算复杂度很高，但它为其他约减算法提供了性能基准。

2.4 核心计算问题

最短向量问题（SVP）

定义 2.6 最短向量问题（SVP）：给定格 $L$，找到非零向量 $\mathbf{v} \in L$ 使得 $|\mathbf{v}| = \lambda_1(L)$，其中 $\lambda_1(L) = \min { |\mathbf{v}| \mid \mathbf{v} \in L \setminus {0} }$。

SVP 是格基约减的核心问题，它在密码学和计算数学中有广泛应用。由于 SVP 是 NP 难问题，实际应用中通常考虑其近似版本：

定义 2.7 近似最短向量问题（ASVP）：给定格 $L$ 和常数 $\gamma \geq 1$，找到非零向量 $\mathbf{v} \in L$ 使得 $|\mathbf{v}| \leq \gamma \cdot \lambda_1(L)$。

定义 2.8 层级最短向量问题（HSVP）：给定格 $L$ 和整数 $k$（$1 \leq k \leq d$），找到 $k$ 个线性无关向量 $\mathbf{v}_1, \ldots, \mathbf{v}_k \in L$ 使得 $|\mathbf{v}_i| \leq \gamma \cdot \lambda_i(L)$ 对所有 $i$ 成立。

最近向量问题（CVP）

定义 2.9 最近向量问题（CVP）：给定格 $L$ 和目标向量 $\mathbf{t} \in \mathbb{R}^n$，找到向量 $\mathbf{v} \in L$ 使得 $|\mathbf{t} - \mathbf{v}| = \min { |\mathbf{t} - \mathbf{u}| \mid \mathbf{u} \in L }$。

CVP 与 SVP 密切相关，许多 SVP 算法可以直接应用于 CVP。在密码学中，CVP 是许多加密方案的基础，如基于格的加密和签名方案。

三、LLL 算法深度解析

3.1 数学基础与核心假设

Lovász 条件的数理推导

LLL 算法的核心是 Lovász 条件，它是一种松弛的正交性条件，确保算法的多项式时间复杂度。

定义 3.1（LLL 约减基）一个格基 $B = [\mathbf{b}_1, \ldots, \mathbf{b}_d]$ 被称为 LLL 约减基，如果满足以下条件：

1. 大小条件 (Size-reduced): 对于所有 $j < i$，有 $|\mu_{ij}| \leq 1/2$。
2. Lovász 条件: 对于所有 $i = 2, \ldots, d$，有：

$$ |\mathbf{b}i^*|^2 \geq (\delta - \mu{i,i-1}^2) |\mathbf{b}_{i-1}^*|^2 $$

其中 $\delta$ 是一个参数，通常取 $1/4 < \delta < 1$。

...