碧海中倒映着青天，
格的基本概念
离散数学中 格是一个满足每两个元素都有最大上界和最小下界的偏序关系(partial ordering)集。
线性代数中，我们将整数环上 \(Z_{q}\) 一组大小为 \(k\) (\(k \leq
n\)) 且线性无关的向量，称为一组基。如果 \(k = n\)，则称该组基是满秩的。
该组基整系数线性组合所有向量的集合（ \(v_{i} \in Z_{q} ，L = \{v_{i} \cdot
M\}\)），称为一个格。
举个例子：
在中国象棋中，象可能到达的坐标集合假设棋盘无限大且没有楚河汉界的存在就是一个格。
直观上看，在棋盘上有很多格点是象无法到达的（比如其初始位置周围一圈皆然）。数学的角度来说，我们可以认为象移动向量的基就是 \(v_1 = (2,2), v_2 = (2,-2)\)。
而 \(v_1\) 与 \(v_2\) 的线性组合就是象能到达的所有点，形如 \(L = \{(0,0),(2,2),(2,-2),(4,0),(0,4) ... \}\)
“格”之名即来源于这些结果向量都是离散而非连续分布的；以点的方式表示之，就像一个个格点。
格中的困难问题
现代密码学中，很多数学工具的应用依赖于其中的“难题”。格中比较重要的难题有两个：
SVP(Shortest Vector Problem)：
CVP(Closest Vector Problem)：
格基规约算法
格基规约简介
格基规约，就是对一组给定的格基进行数学处理，来获得一组“简化”的基向量，这组基构成的格和原基构成的格相同。
具体地，假设原格基是 $ M = {v_1,v_2,v_3,...,v_n}$，
为令新格基 \(M^{'} =
\{v_1^{'},v_2^{'},...,v_n^{'}\}\)
组成的格与原格相同，则新格基应当由原格基和整数域上的矩阵相乘而得（即，\(v_i^{'}\), $i [1,n] $
都能表示成原格基的整系数线性组合）。
而格基规约的目标是在满足上述条件的前提下，令新格基的模(norm)尽可能短（即，获得新格基的各向量长度尽可能短）。
依然举一个比较直观的例子：
考虑一个由基 \(v_1 = (0,1), v_2 = (1,1)\) 组成的二维格。不难发现所有整数坐标的格点都在这个格上。
对 \(M = \{v_1,v_2\}\) 进行格基规约的结果是 \(M^{'} = \{v_1^{'} = (0,1),v_2^{'} = (1,0)\}\)。
可以发现新的这组基更短，质量更高。
二维空间下的格基规约
在二维空间中，格基规约的算法最早由高斯提出，其计算过程非常近似于施密特正交化(Schmidt Orthogonalization)。不同的是：
- 由于格基规约的运算均在整数环上进行，因此对于施密特正交化步骤中的“比例”计算应当取整处理（这也提示了格基规约得到的向量组是高度正交化的，但不保证是正交矩阵）。
- 格基规约本质上是一种贪心算法，计算思路类似于欧几里得算法，即不断地将两组基互相约减，直至满足循环结束的条件。
碧海——格的“增广”攻击
青天——从方程组中提取系数而构造的“短格”
从NTRU入门“短格”
利用“青天”之术，尝试一下对NTRU(Number Theory Research Unit)的攻击：
对既有密码体系的攻击——以Wiener's Attack的格形式为例
春滋——基于格问题的后量子密码体系
AGCD问题
AGCD问题，全称Approximate Greatest Common Divisor Problem。