基

学过线性代数应该知道，一组基是由各个线性无关向量组成。

例如在直角坐标系中，任何一个向量都可以由(1，0)和（0，1）这两个向量任意组合而成，那么称这两个向量为基底向量。

三维空间中，基底向量为（1，0，0）和（0，1，0）和（0，0，1）。

扩展到n维空间，就有基底向量（1，0，0，……，0），（0，1，0，……，0），……（0，0，0，……，1）。

当然基底向量并不是唯一的，只要是一组线性无关向量，并且满足空间中任一项量能由该组向量表示，就可以称为基向量。

矩阵

矩阵可以理解为一组向量的集合，即矩阵$$A = \{\vec{i_1}，\vec{i_2}，……,\vec{i_n}\}，$$$\vec{i_j}$为m维向量，$j∈[1,n]$。
$$
A =\left[\matrix{\vec{i_1}\\vec{i_2}\\…\\vec{i_n} }\right]
=\left[
\matrix{
a_{11}&a_{12}&…&a_{1m}\\
a_{21}&a_{22}&…&a_{2m}\\
\\…&…&…&…\\
a_{n1}&a_{n2}&…&a_{nm}\\
}\right]
$$

格

格可以理解为n维空间上的基向量的线性组合，仍可认为是一个向量，表示形式为矩阵。

举个例子：

格$L=\{a_1\vec{r_1}+a_2\vec{r_2}+…+a_n\vec{r_n}|a_i∈Z\}$，可表示为

$$
L =\left[\matrix{a_{1}&a_{2}&…&a_{n}\}\right]
\left[\matrix{\vec{i_1}\vec{i_2}\…\vec{i_n} }\right]
=\left[
\matrix{a_1\vec{r_1}+a_2\vec{r_2}+…+a_n\vec{r_n}}\right]
$$
但是，并不是所有的向量都是格。（这个有点不好表述）

例如，整数格如下所示：

$\vec{AC}$是整数格，但$\vec{AB}$不是整数格。

可以把格理解为某空间中特定的点，例如只能是下图当中已标好的离散的点：

格的Determinant

格可以写成矩阵的形式，于是它的Determinant（行列式）代表其行列式的值，但一般不叫作行列式，而是组成格的向量所围成图形的面积或者体积。

最短距离

最短距离$λ$表示格中点与点之间的最短距离。
$$
λ_1 = min||\vec{x}-\vec{y}||,\vec{x},\vec{y}∈格L,\vec{x}≠\vec{y}\\
=min||\vec{x}||,\vec{x}∈格L,\vec{x}≠\vec{0},\vec{y}为原点o
$$
记$λ_i$为第i短的距离，则有$λ_1≤λ_2≤…≤λ_n$。

距离函数

任意一个点t（可以不在格L上）到最近的格点的最短距离的函数，记作$μ(t，L)$。

覆盖半径

以格L中所有的格点为圆心，逐渐扩大其半径，使得能覆盖整个空间，此时的半径就是覆盖半径$μ$。

格密码中的一些难题

最短向量问题（SVP）

给定格$L$中的一组基$B$，找到这组基构成的一个格点$Bx:x$，使得该格点到0坐标点的距离最近，即
$$
||\vec{Bx}|| = λ_1
$$

可以理解为找到一组整数$[x,y]$，使得新构成的向量
$$
\vec{Bx} =\left[\matrix{x&y\}\right]
\left[\matrix{\vec{a}\\vec{b}\}\right]
=x\vec{a}+y\vec{b}
$$
满足$||\vec{Bx}-\vec{0}|| = ||\vec{Bx}||=λ_1$。