|
数学辞典:
具体化
一:
格的定义:
这里的格是指点格。它是的一个离散子群。特别的,对于
任意加法子群都构成一个格,这样的格成为整格(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;}
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 17:31
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社