本文深入解析格基约减领域核心的 LLL 与 BKZ 算法。内容涵盖格的数学定义、Gram-Schmidt 正交化原理及误差控制、Hermite 常数与 Mordell 不等式等理论基础，以及 SVP 和 CVP 等核心计算问题。文章结合 10 份核心文献，详细阐述了算法的数理推理、实现流程与优化策略，旨在帮助读者攻克理解难点并衔接理论与工程落地。
格基约减是数学和计算机科学中的一个核心问题，其在密码分析、后量子密码学、整数规划等领域具有广泛的应用。随着量子计算的发展，传统的基于数论的密码系统面临被破解的风险，而格基密码学因其抗量子特性成为后量子密码学的重要研究方向。
LLL 算法（Lenstra-Lenstra-Lovász 算法）和 BKZ 算法（Block Korkine-Zolotarev 算法）是格基约减领域的两个里程碑式成果。LLL 算法实现了多项式时间复杂度的突破，而 BKZ 算法通过块优化升级进一步提升了约减质量。这两种算法构成了现代格基约减技术的基础，在密码分析、后量子密码等领域发挥着关键作用。
本文基于 10 份格基约减领域的核心文献，全面覆盖 LLL 和 BKZ 算法的基础理论、优化变体和工程实现：
本文的核心目标是：
定义 2.1 设 $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d$ 是 $\mathbb{R}^n$ 中的线性无关向量，由这些向量生成的格 $L$ 定义为：
$$ L = \mathcal{L}(\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}d) = \left{ \sum{i=1}^d a_i \mathbf{b}_i \mid a_i \in \mathbb{Z} \right} $$
其中 $\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d$ 称为格 $L$ 的基，$d$ 称为格的秩。
定理 2.1 若 $B = [\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_d]$ 和 $C = [\mathbf{c}_1, \mathbf{c}_2, \ldots, \mathbf{c}_d]$ 是同一格 $L$ 的基，则存在一个 $d \times d$ 的整数幺模矩阵 $U$ （即 $U \in GL_d(\mathbb{Z})$ 且 $\det(U) = \pm 1$），使得 $C = BU$。
证明：
推论 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 算法中具有重要作用，用于将高维格问题转化为低维子格问题进行处理。
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* 和 μ
几何意义：
在实际计算中，Gram-Schmidt 正交化会受到浮点运算误差的影响。误差主要来源于两个方面：
定理 2.2（误差上界）设 $\hat{B}^$ 是浮点计算得到的 Gram-Schmidt 正交基，$B^$ 是精确结果，则存在常数 $C$，使得：
$$ |\hat{B}^* - B^*| \leq C \cdot \epsilon \cdot |B|^2 $$
其中 $\epsilon$ 是机器精度，$|B|$ 是基矩阵的谱范数。
为了控制误差累积，实际实现中通常采用以下策略：
定义 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 不等式是 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$ 增大时，这个上界会显著改善。
定义 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.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$ 成立。
定义 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 算法的核心是 Lovász 条件，它是一种松弛的正交性条件，确保算法的多项式时间复杂度。
定义 3.1（LLL 约减基）一个格基 $B = [\mathbf{b}_1, \ldots, \mathbf{b}_d]$ 被称为 LLL 约减基，如果满足以下条件：
$$ |\mathbf{b}i^*|^2 \geq (\delta - \mu{i,i-1}^2) |\mathbf{b}_{i-1}^*|^2 $$
其中 $\delta$ 是一个参数，通常取 $1/4 < \delta < 1$。
...
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online