格密码与线性代数

目录

一. 幺模矩阵

二. Gram-Schmidt 正交化

三. 矩阵分解

四. 格基本区

五. 对偶格基

六. 矩阵伪逆

七. 正定矩阵

八. 矩阵转置

九. 奇异值分解（SVD分解）

---

格密码中格基是矩阵，格点是向量。本文章梳理一些格密码常用到的一些线性代数的知识点。

一. 幺模矩阵

对格基乘以整数幺模矩阵，会得到新的格基，该格基形成的格点与原来的格点一样。幺模矩阵满足。幺模矩阵的逆依旧为幺模矩阵。

二. Gram-Schmidt 正交化

将格基的一列看成一个向量，也就是。假定Gram-Schmidt 正交化是按顺序进行的，正交化后记作，可以将看成向量的分量。对格密码而言，最重要的性质则是与垂直。

三. 矩阵分解

对格基矩阵V可作如下分解：

其中为正交阵，为对角阵（对角线的值均大于等于0）,为上三角矩阵且对角线元素的值均为1。

通常格基中的向量都是线性独立的，所以根据线性代数的基础，我们知道这种分解也是唯一的。而且Gram-Schmidt 正交化后向量的长度与矩阵D对角线元素的值是有关系的，也就是，其中为矩阵D对角线元素的值。

四. 格基本区

给定任意格基，可形成格基本区。如果把该基本区进行平移，让原点处于该基本区的中心，也就是所谓的origin-centered parallelepiped，如下：

五. 对偶格基

原格基为，对偶格基为，利用如何公式可计算对偶格基：

通俗来讲就是先对格基求逆，再转置，就是对偶格的格基。整个过程非常丝滑。

其实对偶格Gram-Schmidt 正交化的结果与原来格基也有关系，先上结论：

其实就是向量长度互为倒数，如下：

六. 矩阵伪逆

有些方阵不能直接求逆，这个时候就需要利用伪逆（有的时候也叫Moore-Penrose伪逆）,为方便后续解释，暂时记为。原矩阵和伪逆矩阵需要满足：

反过来也经常利用：

需要注意的是不等于单位阵，但是与互为对称矩阵（其实就是转置相等）。

在格密码中，矩阵和伪逆矩阵的空间是不变的，也就是：

七. 正定矩阵

给定一个对称矩阵，对任意向量，都满足如下不等式：

则称该矩阵为正定矩阵(positive definite)，通常记为

当然，如果不等式改为：

则称该矩阵为半正定矩阵，记为

实际上，正定矩阵一定可以求逆，并且逆矩阵也为正定矩阵，也就是。

但是半正定矩阵不一定可以求逆，只能求伪逆，其伪逆也为半正定矩阵，也就是。

在格密码论文中，如果看到，其实是想表达两个矩阵相减为正定矩阵。这个结论换成半正定矩阵也是成立的。另外，如果原矩阵满足这种不等关系，逆矩阵也有类似的结论。换句话说，如果，可得。

八. 矩阵转置

“七”中谈到的对称矩阵有一个非常简单的实现方式。给定任意矩阵，将该矩阵的转置乘以本身，得到新的矩阵则为对称矩阵。也就是，。另外其实很好证明，这个矩阵则是一个半正定矩阵，因为：

当然，熟悉线代的小伙伴都知道，以上运算要求矩阵B非奇异(nonsingular)。

这个结论可以反推。如果已知某矩阵，那么该矩阵存在平方根，也就是。根据半正定矩阵的性质，任意都存在平方根，而且求平方根的过程多项式时间复杂度内可以解决（比如Cholesky分解法）。

九. 奇异值分解（SVD分解）

奇异值分解，英语为singular value decomposition，经常在格密码中简称为SVD分解。奇异值分解主要是给非方阵准备的，对任意矩阵，可以作如下分解：

其中均为正交矩阵，为对角阵。对角线上的值通常以降序排列，并且每个值均大于等于0。其实实际上，对角线上的值就是矩阵B的奇异值。如果想求最大的奇异值，通常利用如下：

其中,u为任意单位向量。