博文
涉及的格相关理论总结
|
数学辞典：
具体化
一：
格的定义：
这里的格是指点格。它是
的一个离散子群。特别的，对于
任意加法子群都构成一个格，这样的格成为整格（integer
lattice）。
格的具体定义：
Def-1：
设向量
线性无关，
的所有整数线性组合构成
维的格
，记为：
称
是这个格的一组基，并且记
。
如果
，则称格
是满维的（full dimensional）。
格的特点：
（1）离散性：
如果记由基
张成的实空间为：
那么，
仅仅是
中一些排列规整的离散点集。因此
。
（2）格基的多样性
一个实空间可以通过不同的基底表示，同样的，一个格也可以通过不同的基地表示。一个维的实空间可以有任意的个线性无关的向量张成，但是从维格中任意选取个线性无关的向量却不一定能够成这个格的一组基。参看下图：
图中网格都是2维格
中的元素。因为通过
与
的整数线性组合，可以表示出中的所有元素，所以这个格也可以表示成
。但是另外的一组向量，与
，尽管它们相互独立，但是却不能表示成中的所有元素。因此
。
究其原因，有与围成的区域里面包含了中的元素
，该点是无法通过与的整数线性组合表示，因此。所以，就会有这样的问题，什么条件下的不同基可以表示同一个格？
Def-2：
设方阵
，如果
，则称
是幺模矩阵。
Th-1
设
是上的个向量，格
。是
的一组基的充要条件是：存在一个幺模矩阵使下式成立
。
备注：在论文中会有格单元（lattice cell）这个概念。格单元在许多文献中被称为平行多面体（parallelepiped），在别的文献中称为格基本域（fundamental domain of lattice）。
Def-3
格
的单元定义为：
从几何学的观点来看，
就是以格基
为了棱边的空间平行多面体区域。我们称该平行多面体围城的空间大小为单元的容积，记为
。
Th-2
格的单元中不包含这个格的其他元素。
证明：（反证法）
Def-4
格的行列式（Determinant）定义为：
。
记
,则
。可以验证，如果格
是满维的，那么，
。
结合Th-1,有
Th-3
格的行列式与选择的基无关。
证明：
上面表明同一个格的行列式和单元容积都是常数。下面的定理揭示了两者之间的联系。
Th-4
二：
子格：
Def-5
设
和
是两个格，如果
并且
，则称
是的子格。
图中，所有网格的焦点都是的元素，图中的所有的圆点都是的元素。
Th-5：
设
是格中格线性无关的向量，那么
。
Th-6：
设
，
，
，
，则
。
证明：
对偶格（Dual lattie）
Def-6:
设是上的一个格。那么的对偶格
定义为：
。
对偶格也称为极性格（polar lattice）或者互反格（reciprocal lattice）。
假设
维格的一组基是
由于
，
,因此实际上是下面线性方程组的解空间。
由此可见，求一个的对偶格可以转化成为求一个非齐次线性方程组的解。由于
，所以该解空间是
维的。因此可以得到对偶格的如下性质：
1.
如果是上的一个格，则
。
2.
Th-7：
设
是一个满维格，且
，那么
是的一组基。
证明：略
正交格（Orthogonal lattice）
虽然一个
维格具有不同的基，但是这些基都张成同一个是空间
是的子空间。定义格
，则
。如果
，则称是完备的。因此，如果
，则是完备的。
Def-7：
设格的基张成的实空间为，如果
表示的垂直实空间，那么的正交格
定义为：
.
正交格是一个非常特殊的对偶格，首先，中的任意一个向量都是整向量
；其次中的任意一个向量与中的任何一个向量都垂直。实际上是下面线性方程组的解空间与的交集，其中
是格的一组基：
由此可见，求一个格的正交格可以转化成为一个齐次线性方程组的整数解。尽管齐次线性方程组一定有解，但是仅仅由这些解中属于的向量构成。
Def-8
如果格
那么
。
几个概念：
Def-9：
设
，且
，则的逐次最短向量长度
定义为
显然，
也就是格的最短向量的长度。从逐次最短向量长度的定义可以看出，
实际是格中任意
个向量的最小包容半径：在为半径的超球里面，一定至少包含一组格的线性无关向量组。所以有：
Def-10
设满维格，那么Hermite常数
定义为：
式中
表示
的最小上界。
～～～～～～～～～～～～～～～～～～～～～～～～～～～
Minkowsiki第一定理
设格是一个满维格，凸集
对称，并且集合
的容积满足
，那么
。也就是说，集合至少包含两个非零的格向量。
由于
，Minkowski第一定理指出，只要上对称的凸集的容积（包含所有元素的最小空间）足够大，中一定至少包含的两个非零格向量，至少有一个非零向量的长度不大于
。
的情况
Minkowski（闵可夫斯基）第一不等式
引理：
设，，那么
定理：
如果维格满维，那么
Minkowski第二不等式
定理：设
，则
，
。当
时有
推论
如果维格满维，则
Minkowski第二定理
定理：
设
～～～～～～～～～～～～～～～～～～～～～～～～～～～
格上的困难问题：
这些格上的难题在密码设计和密码安全性分析中都有着重要的应用。
格是一个离散的子群，在范数条件下格中必有最短非零向量。在引入格上困难问题问题之前，首先给出如下认识：
定义1：
中向量的欧式范数和中心化欧式范数定义为：若
，则的欧式范数
为
而的中心化欧式范数定义为
其中
由于格是离散的，所以格中必有最短非零向量，这个向量的欧式范数称为格的第一最小，记为
或
。更一般的，对于所有的
，Minkowski（闵可夫斯基，德国人）的次最小
定义为：
其中最小值取自中格线性无关向量
构成的向量集合。
称为的逐次最小。……
定义2：
令
是一个中心在原点、半径为
的维开球，则秩为的格
中的逐次最小
定义为：
即：第个逐次最小
，是中心在原点包含个线性独立格向量的最小球体的半径。
特别地，
是格上最短的非零格向量，即：
下面引入逐次最小的两个定理：
定理1：
设是格上的一组基，
是其对应Gram-Schmidt正交基。则格中第一个逐次最小满足
证明：略
定理2：
设秩为的格中的逐次最小为，则存在线性独立向量
，满足
，其中
在介绍完格上逐次最小后，下面简介格上的几个基本定理。
定理1：
（Blichedldt定理）：对任意格上的可测集
，如果的体积
，则存在两个不同的点
满足
。
定理2：
设秩为的格，格上关于原点对称的任意凸集，如果的体积
，那么中包含一个非零格点
。
定理3：
（Minkowski第二定理）：对任一秩为的格，逐次最小满足
。
在以上几个定理的保证下，我们对格困难问题进行探究。在格困难问题主要有最短向量问题（Short Vector Problem ，SVP）、最近向量问题（Close Vector Problem CVP）和最小基问题（Smallest Basis Problem，SBP）。
定义1：（SVP）：
给定一组格基
，找到一个非零格向量
，
，使得对于所有
，有
。
定义2：（CVP）
给定一组格基和一个目标向量
，找到一个与目标向量
最近的格向量，使得对于所有
有
。
具体讨论这两个问题时，可将其转化为三个不同的问题：
（1）
搜索问题：找到一个非零格向量
，满足
（SVP中对应
）最小。
（2）
优化问题：在（对应
）上找到一个（SVP中对应）的最小值。
（3）
判决问题：给定有理数
，判断是否存在一个非零格向量 满足
（SVP中对应
）
上面的三个问题的困难性是一致的，所以在实际应用中，针对具体情况选择一种问题讨论即可。
由于SVP和CVP的困难性，在计算上讨论的均是近似解的求情况，在后面的讨论近似算法返回的解也仅指以指定逼近因子
达到最佳。下面给出近似SVP和CVP的定义。
定义3：（Approximate Shortest vector problem近似SVP）：
给定一组格基，找到一个非零格向量，，使得对于所有，有
。
定义4：（Approximate Closest Vector Problem 近似CVP）
给定一组格基和一个目标向量，找到一个与目标向量最近的格向量，使得对于所有有
。
…………………………
在解决上述格问题时。与所选的基有直接关系的。我们可以通过二维空间的一个例子来观察。
对最短向量问题（SVP）
对于给定的网格和其上的一组基
，寻找网格上的最短非零向量。
（SVP二维空间中选择不同的基对结果的影响）
对最近向量问问题（CVP）
对于给定的网格和其上的一组基，给出某一向量
，寻找网格上的另一个非零向量
，是向量
和向量的距离最短。
（CVP二维空间选择不同的基对结果的影响）
（以上两图说明，选择不好的基找不到最近的格点）
从以上的图可以看出，使用不太好的基时，可找到的最近网格点不是实际最近的网格点。
格基规约问题：
Normal 0 7.8 磅 0 2 false false false MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:普通表格; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}
https://blog.sciencenet.cn/blog-791668-622565.html
上一篇：广义电路
