格是我很感兴趣的内容，会尽可能详细地学习。
一.为什么要研究格
1.格理论相关的数学困难问题可以构造密码，并且其能够抵抗量子计算机的攻击，这为未来的密码方案提供保证。
注：格的困难问题的基本思想在于，将一个格点在多维空间内移动至另一个位置，在不知道移动轨迹的情况下是非常难确定其原本位置的。
2.格理论用于密码分析学，可以破解传统密码方案，比如LLL算法可以用于对特定参数的RSA进行破解，这可以为传统密码的安全性进行评估。
3.格求解的困难程度可以与已知的困难问题相等价，比如对应大数分解、离散对数问题；这可以科学地证明格密码的安全性。
注：（1）安全性证明是指将一些新的密码构造的数学困难性规约到已知的一些数学困难问题上，这样就可以验证密码系统的安全性；同时，安全性证明可以确定某些参数的取值范围（什么取值更安全）。（2）传统密码的安全性证明一般是基于平均情况进行证明的，比如RSA选择的大数N难以分解，只是一部分情况，也有一些特殊的N是有特定算法分解的。
平均情况困难性：类似于双射，一一对应，只能证明某些参数值对应的密码方案是安全的或者有漏洞的，比如RSA的某些n值易被分解。
糟糕情况困难性：类似于完全映射，每一个任意的格（的困难问题），可以映射到所有的密码函数，所以如果当发现一部分的密码函数被破解了，那么所有基于任意格的困难问题都可以被破解。
举例：
1 | 已知x^2 mod N 求x 这个问题可以规约为大整数分解困难问题，这就验证了其安全性 |
4.格可以实现一些传统密码无法实现的特性，比如全同态加密。
5.格密码的加解密效率较高，计算开销很小。
二.什么是格
格可以理解为高维空间内的点集，点的排布呈周期性规律。
与空间向量联系起来，格则是由一组基础向量的无数个整数倍数线性组合构成的向量的终点，也就是无数个离散点。
三.格的定义方法
1.利用格基来表示格
格的基是一组线性无关的向量，由这一组向量可以生成完整的格，也就是可以由他们的线性组合构成所有的格点。
格的基是多样的，在二维空间中，若确定一个格点为原点，以原点出发连接其余任何n个格点所得的n个向量都可以作为格的基。同理，不同的基可以生成同一个格。
通常用L(B)来表示格，把B看作一个矩阵，矩阵的列就是基向量。
2.利用子群定义格
另一种定义方式不需要考虑格基，而是把格定义为R^n下的离散加法子群。
例如，所有模5下和为0的整数点构成格。
四.格基的等价变化
如何判断两组格基可以生成同一个格，换而言之，对一个格基做什么样的变换以后其仍然可以生成原来的格。
如果把格基用矩阵表示（列向量为每一个基），则对格基做以下操作，对应的格不变：
1.列向量交换：vi <——> vj
2.向量取负：vi <—— -vi
3.给一个向量加上k乘另一个向量：vi <—— vi + k.vj
更加有趣的是，上述操作均对应为给格基矩阵右乘一个幺模矩阵，幺模矩阵是一种特殊矩阵，其为整数矩阵，其行列式的值为正负1，且这种矩阵的乘法具有封闭性，幺模矩阵的乘积仍为幺模矩阵。
定理：两个格基等价，当且仅当可以把两格基写成以下格式：
其中，U是一个幺模矩阵。
五.格的基本区域
1.基本区域定义及模算法
基本平行多面体定义为线性无关向量的线性组合（其中系数取值为0到1）组成的点集合，它也是格的基本区域，因为当把这个区域分别放置在不同格点上时，将会组成整个格的面积区域。这非常容易理解，因为格点是整数坐标，而多面体是基的[0,1]系数组合而来，这两者组合起来就能得到所有的实数系数，就得到整个平面。寻找空间中一个点的表示，实际上就是在做模平行多面体的运算，因为在空间中的点的特征，可以映射到格的基本区域中去，因为整个格可以看作基本区域不断平移所得。（注意，当选取一些奇怪的形状作为基本区域的时候，只要能覆盖整个格面，也是可以的，但是这样的区域通常不方便密码学研究）
基本区域的表示方法：ai in [0,1)
假设现在在空间有一个点，表示为：ai为实数
那么当对这个点做mod基本区域的操作之时，只需要把每个系数ai模1乘上基向量即可：
这样做就把这个点映射到基本区域上来，对此可研究他的性质（其各性质与基本趋于的对应点一致）。这种研究思想主要是为了搞清楚空间的点和格的关系，比如点在格上或点不在格上，这样取模研究就不需要知道点的具体位置，只需要把他取模映射到基本区域。比如，任何格点取模以后都会映射原点0。
2.基本区域的一些性质
a.基本区域可以代表整个格的性质
b.基本区域（无论什么形状的)面积都一样，这个结论由基本区域放在各个格点上面组成整个格面可以推导。
3.行列式
行列式：基向量构成的多面体的体积（标量），也就是基本区域的体积。
同一个格选取不同的格基，这个标量值也相等；证明思路容易：
两个基生成同一个格，当且仅当两者可以乘一个幺模矩阵相互转换，那么：
|det（BU)| = |det(B)det(U)|=|det(B)|
行列式衡量了格的密度大小，若行列式较大，则证明格点比较稀疏，密度较小。
4.施密特正交化
有序向量集合：向量次序有先后之分，目的是为了将后边的向量投影到前面的向量上。但一些格点对应的向量投影（分解）以后就不再是格点了。关于施密特正交化：百度百科
上图是把斜向上的格基投影到横着的格基和垂直的向量上，再将向量都除以一个长度，这样就得到新的基（单位向量——R^n的基，但不一定是格点和格基）。
下图的表示方法实际上是格基的另一种矩阵表示法，每个列向量都是格基。比如，|v‘1|是上图横着的向量的长度，其余行为0。|v’2|则是上图蓝色向量的长度，*代表非0数，因此第二列实际上就是原来投影前的另一格基。
QR分解的两个结论：
1.由v1，v2…vn为格基构成的格的基本区域（行列式）就等于v’1,v’2…的乘积，上三角矩阵的行列式为对角线之积。
2.最短非零向量不小于最小的v’i（范数）的长度。证明思路为当若干个非全零系数乘上每一列时，总会有最靠右边的非0列出现，那么该非0列一定会有一个v‘j无法被消去，即格向量至少为这个值，证明结束。（这个结论与LLL算法相关）
六.Minkowski定理
1.Blichfeld定理
当在格向量空间任取一个大于格的基本区域的体积的空间s时，一定能在s中找到两个点，其相连构成的向量为某个格点（向量）。下面这个袋鼠很形象：
2.Minkowski
任取一个格，在其上取一个集合s，这个s是有条件的：
1.s是一个凸集合
2.s的空间关于原点对称
3.如果s体积足够大，不仅要大于行列式，还要大于2^n乘行列式
满足这样条件的s中一定有至少一个非0格点
证明：
同时对s的n个维度的长度缩小2倍，那么s的体积缩小2^n倍，但是这样的s仍然大于基本区域，根据Blichfeld定理可知，在现有的s内仍然还存在格点向量，因此一定有非0格点在区域内。
推论：
取任意一个格，格的最短向量不会超过$\sqrt[n]{det}*\sqrt{n}$
对于任意行列式为1的格，必然包含一个长度不超过根号n的最短向量（可以在二维平面作图理解），更严格的证明为：取一个半径为$\sqrt{n}$的球，其体积大于内部的棱长为2的立方体（体积为2^n）
七.格中的困难问题以及密码体制
非困难问题：
1.已知基和一个向量v，验证v是否在格L中
将v用基来表示，观察系数是否为整数，若为整数，则v在格中。
2.给定两组格基，判断两者生成的格是否等价
公式B1 = B2*U 或者检查其中一组基向量是否都为另一组格中的向量，当然还需要反过来检查另一组的基是否为第一组的格向量；若满足则两者等价。
困难问题：
1.SVP（shortest vector problem）
找到格中的最短向量，或者近似最短向量长度，或判定其长度范围。（注意这里的近似一般都用最短的r倍来衡量）
2.SIVP（shortest independent vector problem）
求n个最短线性无关向量，或其近似值。
3.CVP（closed vector problem）
给一个点，要找到离该点最近或近似最近的格点。SVP并不比CVP更困难，也就是如果能解决SVP，则CVP可以解决。比如二维空间中，找一个最短向量可以理解为找离原点最近的非零向量。