格的逐次极小

从原点逐渐放大一个球。球第一次碰到非零格点的半径是 ${\lambda }_1$；继续放大时，同一直线上的更多倍点不会增加维数，直到出现一个新方向才到 ${\lambda }_2$。如此反复，${\lambda }_k$ 标记球内首次有足够方向张成整个 $V_{\mathrm{\Lambda }}$。

因此逐次极小记录的不是“第 $i$ 短的点”。格点成对出现且同一直线上有无穷倍数，按长度排序会把许多重复方向算进去；逐次极小只在新增独立方向时前进。它把格的各向异性压缩成 $k$ 个尺度：若 ${\lambda }_1$ 很小而 ${\lambda }_k$ 很大，格在某些方向密、另一些方向稀。

这些尺度对换基不变，因为定义只看点集和内积。输入基可能极坏，却不能改变任何 ${\lambda }_i$；算法的任务正是从表示中揭示这些固有几何量或其近似。

对

向量 $(\pm 1,0)$ 长度为 $1$，故 ${\lambda }_1=1$。半径小于 $3$ 的所有格点都在横轴上，不能给第二个方向；半径达到 $3$ 时 $(0,\pm 3)$ 出现，所以 ${\lambda }_2=3$。点 $(2,0)$ 虽是“另一个短格点”，却不增加 span 的维数。

取 $\mathrm{\Lambda }={\mathbb{Z}}^2$，向量 $(1,0)$ 与 $(1,2)$ 线性无关，最长为 $\sqrt{5}$，但它们生成指数 $2$ 的子格。逐次极小并不要求所选独立向量构成基；事实上本例真正的 ${\lambda }_2=1$，可由 $(1,0),(0,1)$ 达到。这一区分在由短独立向量推断短基时尤其重要。

若把范数换成 ${\ell }_{\mathrm{\infty }}$，同一个格的数值可能改变；若把闭球换为开球，临界半径处是否“取到”也会改变形式。计算复杂性结论必须写明范数、近似因子与输入编码，不能只写“求逐次极小”。

Minkowski 第一定理理路格上的 Minkowski 第一定理Minkowski's first theorem for lattices · Minkowski convex body theorem · Minkowski 格点定理体积超过格基本区域两倍幂的中心对称凸体必含非零格点。以余体积给出 ${\lambda }_1$ 的上界，第二定理进一步控制 $\prod _i{\lambda }_i$ 与格余体积的比值。最短向量问题理路最短向量问题Shortest vector problem · SVP · 格最短向量问题从格基寻找达到或近似第一个逐次极小的非零格向量。正是寻找达到 ${\lambda }_1$ 的向量；SIVP 则要求输出 $k$ 个独立向量，其最大长度在 ${\lambda }_k$ 的给定近似因子内。

解码中，${\lambda }_1/2$ 是任意两个不同格点的开球不相交所允许的临界尺度。密码归约经常同时出现 ${\lambda }_1$、${\lambda }_k$ 与对偶格的逐次极小；它们承担不同量词，不能统称为“格中短向量”后互换。