什么是格？
由于这个问题很是坚苦，自然要思量这个问题的一个放宽问题，即近似最短向量问题。所谓近似问题，就是并禁绝确求出该问题，，而是某一范畴内。
在暗码学中，人们常常思量是多项式格维数范畴之内的近似因子γ。今朝已知最好的多项式时间内求解近似SVP问题的算法，其近似因子都是亚指数格维数范畴内。也就说求解出的向量长度并不短，尽量在有限时间内。反之，假如你想求解出多项式格维数范畴之内的近似因子γ，即求解出长度不高出γ的格向量中找到一个非零短向量，其求解时间将不是多项式时间了。
这引出了格中的第一个根基坚苦的问题，即最短向量问题（SVP）。给定格的一个基，问题就是在格中找到一个非零向量，该向量的长度在所有非零格向量上最短。
子空间一词汇报我们，假如您的格中有两个向量，那么你可以几许地从另一个向量中减去另一个，而最终的位置将是格中的另一个向量。这意味着零向量始终在格中。每个格都有一个基，但它远不是独一的，实际上每个格都有无限的数量，并且并不是所有的格都一样好用。回到我们的示例格，我们可以添加一些基，在这种环境下是向量对：其实暗码学家更感乐趣的是判定问题。下一期将表明该问题。
再反复说一遍，必需找到一个长度为的向量，个中是λ的最大大概值，λ可以对上面所述的离散性举办表明。众所周知，对付随机归约来说，这个问题是NP坚苦问题（非确定性多项式坚苦问题）。
在数学中有两个完全差异的工具都称为格，我们此刻说的格是界说为向量空间的离散子空间。在此，离散意味着在格中不能存在任意互相靠近的两个向量。换句话说，存在一个正实数λ，使得格中的任何两个向量都不能小于间隔λ。
在视觉上，二维的格看起来像这样，每个点不是持续的，而是离散的：
直观上，我们可以留意到蓝色和绿色的基向量比黄色或紫色的基向量要悦目（向量较量短）。实际上，利用短向量意味着利用较少的存储来描写格。在二维空间中，求短向量并不是一个坚苦问题，可以利用Lagrange算法求短向量。可是跟着维数的增加，在随机给出一个基的环境下，求解该问题将会变得很是坚苦。
这里，给了一个近似因子γ，只需要在长度不高出γ的格向量中找到一个非零向量。
格上的根基问题
间隔发生美，格是具有很好性质的数学工具，因为它们可以用相对少量的数据来描写。凡是利用的描写是给特此外基，基是由若干向量构成的。通过这些基本向量的整数线性组合来生成所有其他点。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
