,要求找出最接近于该矢量的格点,即那组基。两个问题相比之下,CVP比SVP要更加难以解决。因为精确的SVP问题是属于NP问题,即多项式时间困难问题,但它在实际中需要的地方并不多,所以以下的近似SVP问题被提出。Р近似SVP问题的定义为:给定秩为d的格L基B,近似因子为,要求找出非零矢量,使得满足以下条件:。它可以简单记为apprSVP。截止到目前为止,已经能够证明apprSVP问题是NP难得当且仅当近似因子。Р3.2格基的规约Р下面给出一些格基规约的相关概念:Р对任何矢量集,是由生成的线性空间,或者称之为包含S的的最小子空间。Р如果设是格的一个格基,于是它的Gram行列式可以表Р示为是阶Gram矩阵。Р关于Gram行列式有一个很重要的在几何学上的解释,即当线性无关,矢量生成的平行多面体为:Р,Р则是该平行多面体的体积,可以记为。Р设表示半径是r中心在原点的n维开球,简记为。Р子空间,它的正交补可以表示为。用表示向量在上的投影,那么当时,,当时,。Р当是一个格,则的秩被定义为的维数,当时格称为满秩格。Р和的线性子空间类似,格的基也补唯一。两者的不同点集中在,不是所有的最大线性无关矢量都能构成一个基。Р任意一个格都有无数格基。设为格的某一个格基,矩阵,任意个格矢量,矩阵为C,如果存在可逆的矩阵满足,并且,那么也是格的一个基。显然有无数格矩阵U满足条件。Р设是的子格,我们称是的本原子群,其中,且。同理,定义本源矢量,要求该组矢量可以扩充成的一个基。这个SVP问题一样,每一个格都存在最短非零矢量,且不唯一。Minkowshi给出了最短非零矢量的长度的定义,其定义为格的第一最小值。又由于定义第二短矢量不具意义,所以Minkowshi限定了最短矢量的定义为线性无关的格矢量。Р3.3格基规约的基本定义和定理Р定义3.1 逐次最小值(The essive minima) 格的第i个次最小值
全文预览
