整理日期：2026-10-16。 适用范围：格基约化中的投影格、局部短向量计算，以及它们与筛法维数和向量提升的关系。 前置笔记：02 基本区域、格行列式与正交化、05 格基约化与 LLL 算法、06 Babai 最近平面算法与近似 CVP、15 高斯启发式与随机球面模型。
设 \(B=(b_1,\ldots,b_n)\in\mathbb Z^{n\times n}\) 满秩，\(\Lambda=\mathcal L(B)\)。沿用列基与欧氏范数，记 \(b_k^*\) 为 GSO 向量，\(g_k=\|b_k^*\|\)。
本篇使用从 \(1\) 开始的下标，区间 \([i,j]\) 包含两个端点。
1. 投影格与局部块#
定义 \(\pi_i\) 为到前缀空间 \(\operatorname{span}(b_1,\ldots,b_{i-1})\) 的正交补上的投影：
$$ \pi_i(x)#
x-\sum_{k<i} \frac{\langle x,b_k^\rangle}{g_k^2}b_k^. $$
特别地，\(\pi_1\) 是恒等映射，且
对 \(1\le i\le j\le n\)，定义局部投影基及其生成的格：
$$ B_{[i,j]}#
\bigl(\pi_i(b_i),\ldots,\pi_i(b_j)\bigr), \qquad \Lambda_{[i,j]}=\mathcal L(B_{[i,j]}). $$
投影后的这些向量仍线性无关，所以 \(\Lambda_{[i,j]}\) 是维数为
的格。特别地，\(\pi_i(\Lambda)=\Lambda_{[i,n]}\)。
这里的投影与格基前缀相配合，保证了投影后的离散性；任意子空间上的正交投影并不一定把格映成格。局部格位于投影空间中，其向量通常不属于原格。
这一记法对应 G6K，EUROCRYPT 2019，§2.1，PDF 第 6 页的 local projected basis；原文使用从 \(0\) 开始的下标和右端点不包含在内的区间，阅读时需换算。
2. 局部长度、体积与高斯启发式#
局部基 \(B_{[i,j]}\) 的 GSO 向量正是
原因是：先消去前缀方向，再对剩余列正交化，与完整 GSO 的对应步骤一致。
因此，局部格在自身张成空间中的体积为
$$ \boxed{ \det(\Lambda_{[i,j]})#
\prod_{k=i}^{j}g_k. } $$
它一般不同于未经投影的子格 \(\mathcal L(b_i,\ldots,b_j)\) 的体积。全格行列式由全部 GSO 长度的乘积给出；局部计算只使用相应区间。
对整数系数 \(z_i,\ldots,z_j\)，有
以及
$$ \boxed{ |y|^2#
\sum_{k=i}^{j} \left( z_k+\sum_{\ell=k+1}^{j}\mu_{\ell,k}z_\ell \right)^2g_k^2. } $$
这个式子由正交分解直接得到，说明局部 SVP 的长度计算需要 GSO 长度和投影系数 \(\mu\)；只知道体积，不能确定哪些整数系数组合最短。
沿用第 15 篇的参考长度定义，令 \(V_d\) 为 \(d\) 维单位球体积，则
$$ \boxed{ \operatorname{gh}(\Lambda_{[i,j]})#
\left(\frac{\prod_{k=i}^{j}g_k}{V_d}\right)^{1/d} \approx \sqrt{\frac{d}{2\pi e}} \left(\prod_{k=i}^{j}g_k\right)^{1/d}. } $$
最后一个近似用于较大的 \(d\)。它估计的是这个局部格的长度尺度，所用维数和体积都应来自当前局部块。
3. 局部 SVP 与 BKZ 约化条件#
局部 SVP 的输入是 \(B_{[i,j]}\)，目标是寻找
求解器还应返回相对于局部基的整数系数 \(z_i,\ldots,z_j\)，以便恢复对应的原格向量。
BKZ，全称 Block Korkine–Zolotarev，使用块大小参数
在位置 \(i\)，取
由于 \(b_i^*=\pi_i(b_i)\) 本身就是局部格中的非零向量，总有
理想的精确 BKZ 条件要求基满足尺寸约化，并且每个位置都有
也就是：在该位置允许考虑的投影块内，第一条投影基向量已经最短。定义见 G6K，§2.2，Definition 1，PDF 第 7 页。
算法中通常使用带松弛的条件，例如固定 \(1/4<\delta<1\)，要求
它允许第一条投影基向量比局部最短向量稍长，并给出明确的改善阈值。
对同一组基，增大 \(\beta\) 会扩大局部搜索空间，使约化条件更强，通常也提高局部求解成本。当 \(\beta=n\) 时，精确条件成为 HKZ 条件，且 \(b_1\) 是全格最短向量；一般的较小块条件只约束相应的局部问题。
4. 从投影向量到原格向量：Babai 提升#
设局部求解器得到
使用相同整数系数构造
这给出一个提升，但 \(x_0\) 在前缀方向上的分量可能较长。所有投影到同一个 \(y\) 的原格向量构成陪集
因此，可以通过加减前缀格向量，寻找更短的提升。这正好衔接第 06 篇的 Babai 取整：
x ← x₀
对 k = i−1, i−2, …, 1：
q ← round(〈x, bₖ*〉 / gₖ²)
x ← x − q·bₖ
返回 x每一步保持 \(x\in\Lambda\) 和 \(\pi_i(x)=y\)。结束后，
由正交性，
$$ \boxed{ |x|^2#
|y|^2+\sum_{k<i}\varepsilon_k^2g_k^2 \le |y|^2+\frac14\sum_{k<i}g_k^2. } $$
这是将 Babai 残差界用于提升得到的直接推论。逐维提升的同类公式见 G6K，§3.2，Extend Left，PDF 第 9 页。
提升恢复了被投影掉的方向，也增加了相应长度。Babai 给出一个易计算的提升，但不保证它是该陪集中最短的向量。
5. 插入局部解与 BKZ 的基本流程#
找到原格中的短向量后，还需要将它纳入一组仍生成原格的基。
设局部解的系数向量为 \(z=(z_i,\ldots,z_j)^T\)。若 \(y\) 是精确最短非零向量，则
否则可以除去公共因子，得到更短的非零局部格向量。满足这一条件的整数向量称为原始向量，可以补成某个幺模矩阵 \(U\) 的第一列。
于是，对未投影的原基块执行
就能使 \(x_0\) 成为块的第一列，同时保持原格不变。再减去前缀基向量的整数倍，可以得到上一节的 Babai 提升。
在前缀保持不变的这一步，新基满足
所以，BKZ 在位置 \(i\) 比较的是投影长度 \(\|y\|\) 与原来的 \(g_i\)。提升后的完整向量长度与这个局部比较量需要分别记录。若使用非精确求解器，插入前同样需要处理整数系数的公共因子及换基条件。
下面给出一次扫描，也称一轮 tour，的简化结构：
BKZTour(B, β, δ):
B ← LLLδ(B)
对 i = 1, …, n−1：
更新当前基的 GSO
j ← min(i+β−1, n)
(y, z) ← LocalSVP(B_[i,j])
如果 ||y||² < δ·gᵢ²：
用 z 构造原格中的提升
通过保持原格的换基，将它插入位置 i
B ← LLLδ(B)
返回 B这里暂将 LocalSVP 视为精确求解器；枚举和筛法是实现局部求解的不同途径。以低维 SVP 改善格基的思路，也见 Micciancio《Blockwise Basis Reduction》，Fall 2025，第 4 页。
一次插入及后续 LLL 可能改变其他窗口，因此通常需要多轮扫描。实际实现还会指定局部预处理、搜索成功率、目标半径及停止规则；启发式求解器某次没有找到改善向量，并不证明该局部格已满足精确条件。
6. 全格维数、块大小与实际筛法维数#
现在可以区分三个量：
- 全格维数 \(n\)：原始格的秩。
- BKZ 块大小 \(\beta\)：局部窗口的名义上限；当前位置的实际块维数为 \(d=\min(\beta,n-i+1)\)。
- 实际筛法维数 \(s\)：本次向量池所在投影格的维数。
直接在整个局部块中筛法时，\(s=d\)。如果选取整数 \(0\le f<d\)，先投影掉块内前 \(f\) 个方向，只在
中筛出候选，则
随后，可以把候选 \(y\in\Lambda_{[i+f,j]}\) 向左提升为 \(\widetilde y\in\Lambda_{[i,j]}\)。对局部基应用同样的 Babai 过程，得到
这解释了 dimensions for free 的基本思路：把主要的筛法搜索放在较小维数中，再利用提升获得更大块里的短向量。其可行性依赖预处理后的 GSO 长度、候选覆盖范围和提升效果。相关算法与启发式分析见 Ducas，EUROCRYPT 2018，《Shortest Vector from Lattice Sieving: A Few Dimensions for Free》，§3.1–§3.2，Algorithm 2 与 Heuristic Claims 1–2，PDF 第 5–7 页。
这里通常需要考察多个候选：投影最短的向量不一定具有最短的提升。“免费”表示减少昂贵搜索所需的维数，提升本身仍有计算成本和长度代价。
应用第 15 篇的概率与数量模型时，应使用当前筛法空间：
$$ \operatorname{gh}(\Lambda_{[i+f,j]})#
\left( \frac{\prod_{k=i+f}^{j}g_k}{V_s} \right)^{1/s}, $$
球帽概率也相应使用 \(p_s(t)\)，同时保留方向分布和独立性的假设。
7. 与后续筛法研究的联系#
BKZ 负责选择局部问题、调用短向量求解器并调整格基；筛法负责在当前投影格中维护和约化向量池。完整运行成本需要结合局部调用次数、每次的筛法维数、轮数，以及预处理、提升和换基开销。
渐进筛法改变维数时，还会改变向量池的几何状态：
- 向右扩展窗口：旧向量可以直接嵌入更大的局部格，但在新增 GSO 方向上的分量为零。
- 向左扩展窗口：Babai 提升补入一个受取整约束的分量，并增加相应长度。
因此，扩展后的旧向量不会自动成为新空间中的独立均匀样本；局部体积、参考长度和分布假设都需要随窗口更新。G6K 对这些操作及筛法、提升范围的区分，见 §3.2–§3.3，PDF 第 9–11 页。
下一篇进入《17 筛法的基本框架与两向量约化》，具体讨论向量池如何生成、约化、更新和停止，再衔接 Nguyen–Vidick、ListSieve 与 GaussSieve。