格密码学习笔记(三)Determinant

前景回顾

上一篇文章呢，讲述了一些有关于幺模矩阵的知识，我们知道了，格基，如果当且仅当其中为幺模矩阵，那么本文呢，我们来看下格中一个重要的概念，格的行列式，这个值实际上是和基无关的量。

知识回顾

克拉默-施密特正交化

在描述格的行列式之前，我们先来回顾下高代当中的一个重要的方法，施密特正交化(「The Gram Schmidt orthogonalization」)。那么，这是个什么呢，简单来说就是将一组非正交基转换成为一组正交基。

• 「定义1」: 施密特正交化(「The Gram Schmidt orthogonalization」)，施密特正交化是指将一组线性无关的向量然后计算出一组正交基使得$operatorname{span}(mathbf{b}1, ldots mathbf{b}n) = operatorname{span}(mathbf{b}^{star}{1}, ldots mathbf{b}^{star}{n})$，也就是通过施密特正交化，可以得到一组正交基，使得他们张成的向量空间相同。

对于这个概念，其实不难理解，但是如何做到这一点呢，我们来看一下算法过程。

「The Gram Schmidt orthogonalization」算法

❝

输入: 一组向量输出: 一组正交基

❞

算法过程

• 1) 令
• 2)
• 3) ...
• 4) $boldsymbol{b}_{j}^{*}:=boldsymbol{b}_{j}-sum_{i<j} mu_{i,="" j}="" boldsymbol{b}_{i}^{*}="" ,="" mu_{i="" j}:="frac{leftlangleboldsymbol{b}_{j}," boldsymbol{b}_{i}^{*}rightrangle}{left|boldsymbol{b}_{i}^{*}right|_{2}^{2}}="" quad="" forall="" j="1," ldots,="" n$<="" section="">

也就是是在。那么我们还是来看一个例子，我们看一下在下的一个例子吧，我们给定，，效果如下图所示:

为了直观的演示下这一点，这里搞了一个视频，这也是一次尝试，发现做起来还挺有意思，但是因为我比较菜，因此做的不是特别好，凑合看吧，不接受反驳。

这里需要注意的是，进行施密特正交化得到的一组向量，一般不会是格基，也就是说，并不是所有的格都有正交的格基。好了，这里讲完了施密特正交化的相关知识，后面就可以来看格中的行列式了。

格的行列式(Determinant)

• 「定义2」: 格的行列式是所有正交向量长度的乘积，如下所示

通常，我们使用，也就是欧氏距离。特别的，如果说一个格是一个满秩的格，那么他的行列式也就是对应矩阵对应的行列式，也就是。

行列式的计算

• 「定理1」: 对于任意一组格基

「证明:」 根据施密特正交化的过程，我们可以得到一组正交向量使得，其中是一个对角线元素为1的上三角矩阵，在位置的元素值为对于任意的。因此，我们可以得到

注意到上面的约束，可以得到，因此我们只需要计算，因为在当中的向量是正交的，因此我们可以通过如下方式计算

也就是

这里呢，我们就给出了格当中行列式的计算方法。

陪集

接下来，从另一个角度来看一下格的行列式，在介绍之前呢，我们回顾一下陪集的相关概念。

• 「定义3」: 令G是一个群，H < G是一个子群，，则是H的一个左陪集，定义为

说一下我个人的理解，陪集其实完成了对于群的一个划分，a可以看做划分的代表元素。接下来思考一下我们在第一篇文章当中的对于格的另一个定义，也就是在上面的一个离散子群，然后这里我们考虑在上面的格，回顾下在第一篇文章当中讲过的Fundamental Parallelepiped，我们有

• 「引理1」:

证明: 令为格张成空间的一组正交基，显然，线性变换是不会改变体积的，因此可以得到，由于并且是一个n阶的方阵，因此

然后根据引理1我们可以得到证明完毕。

• 「引理2」: ，存在一个唯一的使得

证明: 由于，令是格基当中的向量，由于是空间的一组基，因此存在唯一的标识，使得

然后，我们令

我们可以发现，，因此，也就是

由于这是对于任意在当中的向量，并且，也就是.

目前，我们只是证明了存在，并没有证明是唯一的，我们实际上要证明对于使得。

利用反证法，假设，，注意到，因此可以得到

注意到，是非奇异矩阵，因此，也就是，和假设矛盾，证明完毕。

之前介绍陪集的时候，可以看做是对于原始群的一个划分，对于格来说，每个格向量实际上就是一块空间的一个代表，我们还是用一个视频来看下这个过程。

总结

本次文章，介绍了格当中的一个重要的量，格的行列式，在本文当中，我们提到了一个概念，也就是距离，对于距离来说，测量方式也有很多，那么下一篇文章，我们将对距离来进行展开讲解，老样子，最后还是以道德经结尾吧。

❝

不上贤，使民不争；不贵难得之货，使民不为盗；不见可欲，使民不乱。是以圣人之治也，虚其心，实其腹，弱其志，强其骨，恒使民无知、无欲也。使夫知不敢、弗为而已，则无不治矣。

❞

参考资料

• https://cseweb.ucsd.edu/classes/sp07/cse206a/lec2.pdf^[1]
• https://docs.manim.community/en/stable/index.html^[2]
• https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf^[3]
• https://homepages.cwi.nl/~dadush/teaching/lattices-2018/^[4]
• https://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-2.pdf^[5]
• https://web.williams.edu/Mathematics/lg5/APM461/LS12.pdf^[6]
• https://maki-lab-oss.oss-cn-shanghai.aliyuncs.com/auto/eab038ce2f5343a29afe4d3d8259ddc5.pdf^[7]
• https://eprint.iacr.org/2015/938.pdf^[8]
• https://eprint.iacr.org/2023/032.pdf^[9]
• https://thelatticeclub.com/^[10]
• https://arxiv.org/pdf/1911.00721.pdf^[11]
• https://crypto.sjtu.edu.cn/~wenling/Lattice-Based Cryptography/Part I, CHAP 01 Geometric and Computational Backgrounds.pdf^[12]
• ^{https://github.com/ManimCommunity}
• 道德经 【老子】

Reference