格密码学习笔记(四)

前景回顾

上一篇文章，我们介绍了在格中一个重要的量，格的行列式，那么接下来呢，我们接着来看格当中其他的一些量，本篇文章依然是一个数学元素满满的文章。

知识回顾

上一篇文章，我们提到了有关于距离的说法，我们采用了欧氏距离，接下来我们给出距离的一些计算方法，也就是范数的概念。范数是一个函数，也就是表示从的一个映射满足如下三个性质。

• 只有在时等号成立

其中并且。其中，一个比较重要的范数家族()定义如下

其中，特别的几个我们经常用到，比如范数

再有就是我们之前提及过的范数，也就是欧几里得范数

最后呢，还有一个当p趋向于无穷的时候，有一个也就是无穷范数或者最大值范数

对于无穷范数来说，其实也是用的上面的那个表达式，我们来证明一下

证明: 令，然后

注意到，

我们注意到，n是一个确定的数字，因此根据迫敛性原理，我们可以得到

也就是

好了，先回顾完成范数的相关知识，我们就可以来看今天本文的主题了。

Successive Minima

• 「定义1」: 令是一个在n维向量空间当中中心在原点半径为r的 一个开球，我们定义是第i个包含i个线性无关向量的开球的半径，也就是

这里的范数其实可以指的任意范数，本文开头的视频采用的时欧几里得范数。

根据格是

上面的离散子群，然后就有一个疑问，在格当中是否存在一组线性无关的向量使得，因此特别的实际上就是在格当中的最短向量的长度，也就是

• 「定理1」: 令是一组格基，然后是格的一组正交基(通过Gram-Schmidt orthogonalization得到)，可以得到

这里，我们考虑范数。

证明: 令为格当中的一个非零向量，i使得的最大的索引，我们只需要证明

我们根据的定义，容易得到，因此我们接下来只需要证明，注意到

对于任意的成立，因此我们可以得到

然后，我们如果能证明便可以得到，那么接下来我们来证明一下，注意到

由于，因此可以得到

证明完毕。

总结

由于格是在之上的离散子群，因此自然而然的想到了能不能找到最短的距离，有了最短的，自然那可能就有次短的，以此类推了，就好比世界第一高峰为珠穆朗玛峰，第二高峰是乔戈里峰，第三高峰是干城章嘉峰等等，之后呢，我们找到了最短向量的一个上界，也就是在上一篇文章当中提及的施密特正交化之后的最短向量，那下一篇文章呢，我们来看下，还有没有其他上界。

最后呢，老规矩了，还是以一句老子的道德经结尾了，为了这枯燥的文章，增加一抹文艺色彩。

❝

道冲而用之或不盈，渊兮似万物之宗。挫其锐，解其纷，和其光，同其尘。湛兮似或存，吾不知谁之子，象帝之先。

❞

参考资料

• https://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-2.pdf^[1]
• https://eprint.iacr.org/2015/938.pdf^[2]
• https://arxiv.org/pdf/1911.00721.pdf^[3]
• https://cseweb.ucsd.edu/classes/wi10/cse206a/lec1.pdf^[4]
• 道德经【老子】

Reference