文章目录

• NNN维超球体体积结论
• 闵可夫斯基凸体定理
• 闵可夫斯基第一定理
• 闵可夫斯基第二定理
• 致谢

NNN维超球体体积结论

在nnn维空间中，对半径为rrr的超球体（Ball），有vol(B(0,r))≥(2rn)n\mathrm{vol}(\mathcal{B}(0, r)) \geq \left( \frac{2r}{\sqrt{n}} \right)^nvol(B(0,r))≥(n​2r​)n。如下图所示，当n=2n=2n=2时，半径为rrr的圆里包含一个边长为2r2\frac{2r}{\sqrt{2}}2​2r​的正方形，圆的直径是正方形的对角线，圆的面积大于正方形的面积。

闵可夫斯基凸体定理

定理1 在空间Rn\mathbb{R}^nRn中，对任意对称凸体C∈Rn\mathcal{C} \in \mathbb{R}^nC∈Rn，若vol(C)>2n\mathrm{vol}(\mathcal{C}) > 2^nvol(C)>2n，则C\mathcal{C}C必定包含一个非零整数向量。

注意凸体和凹体的区别
什么是凹多面体，什么是凸多面体，怎么区分，有什么例子？

以下图为例，在二维整数格Z2\mathbb{Z}^2Z2上，将正方形C\mathcal{C}C的中心放在原点，只要C\mathcal{C}C的面积严格大于2n2^n2n，那么C\mathcal{C}C必定包含非零整数点（注意是包含在内而非放在边界上）。

证明略（欢迎补充完整证明）。

闵可夫斯基第一定理

虽然在多维空间求解精确的λ1\lambda_1λ1​很困难，但是存在多项式算法能够快速求解出λ1\lambda_1λ1​的大致上界。

定理2 对任意nnn维满秩格L(B)\mathcal{L}(\bm{B})L(B)，其第一连续极小满足λ1≤n⋅det(L)1/n\lambda_1 \leq \sqrt{n} \cdot \mathrm{det}(\mathcal{L})^{1/n}λ1​≤n​⋅det(L)1/n。

证明： 通过对Zn\mathbb{Z}^nZn施加线性变换B\bm{B}B可以得到对应的格L\mathcal{L}L，即L=BZn\mathcal{L} = \bm{B} \mathbb{Z}^nL=BZn。

图上图为例，在格L\mathcal{L}L上找到以格点为球心、半径为λ1\lambda_1λ1​的超球体B(0,λ1)\mathcal{B}(0, \lambda_1)B(0,λ1​)，该超球体内包含一个体对角线长为2λ12\lambda_12λ1​的立方体S\mathcal{S}S，有vol(S)=(2λ1n)n\mathrm{vol}(\mathcal{S}) = \left( \frac{2\lambda_1}{\sqrt{n}} \right)^nvol(S)=(n​2λ1​​)n。

对立方体S\mathcal{S}S施加逆变换B−1\bm{B}^{-1}B−1转回到Zn\mathbb{Z}^nZn上得到一个凸体C\mathcal{C}C。

易知，vol(C)=det(B−1)⋅vol(S)=det(L)−1⋅(2λ1n)n≤2n\mathrm{vol}(\mathcal{C}) = \mathrm{det}(\bm{B}^{-1}) \cdot \mathrm{vol}(\mathcal{S}) = \mathrm{det}(\mathcal{L})^{-1} \cdot \left( \frac{2\lambda_1}{\sqrt{n}} \right)^n \leq 2^nvol(C)=det(B−1)⋅vol(S)=det(L)−1⋅(n​2λ1​​)n≤2n。否则的话，有det(B−1)⋅vol(S)>2n\mathrm{det}(\bm{B}^{-1}) \cdot \mathrm{vol}(\mathcal{S}) > 2^ndet(B−1)⋅vol(S)>2n，由nnn维超球体体积结论进一步有det(B−1)⋅vol(B(0,λ1))>2n\mathrm{det}(\bm{B}^{-1}) \cdot \mathrm{vol}(\mathcal{B}(0, \lambda_1)) > 2^ndet(B−1)⋅vol(B(0,λ1​))>2n，即超球体B(0,λ1)\mathcal{B}(0, \lambda_1)B(0,λ1​)逆变换后的对称凸体会严格把一个非零整数点包含在内而不是放在边界上，这就与λ1\lambda_1λ1​的定义冲突了。

换算一下，得到λ1≤n⋅det(L)1/n\lambda_1 \leq \sqrt{n} \cdot \mathrm{det}(\mathcal{L})^{1/n}λ1​≤n​⋅det(L)1/n。

证毕。

闵可夫斯基第二定理

定理3 对任意nnn维满秩格L(B)\mathcal{L}(\bm{B})L(B)，有λ1≤(∏iλi)1/n≤n⋅det(L)1/n\lambda_1 \leq \left( \prod_i \lambda_i \right)^{1/n} \leq \sqrt{n} \cdot \mathrm{det}(\mathcal{L})^{1/n}λ1​≤(∏i​λi​)1/n≤n​⋅det(L)1/n。

证明略（欢迎补充完整证明）。

定理3指出全部nnn个连续极小的几何平均数小于等于n⋅det(L)1/n\sqrt{n} \cdot \mathrm{det}(\mathcal{L})^{1/n}n​⋅det(L)1/n，用此约束L\mathcal{L}L的形状。

致谢

• Simons格密码公开课官网

Mathematics of Lattices - Simons Institute for the Theory of Computing

• 哔哩哔哩中英双语视频（字幕组：重庆大学大数据与软件学院 后量子密码研究小组）

【中英字幕】Simons格密码讲座第1讲：格的数学定义_哔哩哔哩_bilibili

• 其它格密码讲解课程和博文

格密码与最短向量上界_唠嗑！的博客-CSDN博客