格相关

格的定义

$$
{设线性无关向量组v_1,v_2,…,v_n \in R^m，该组向量生成的格L即是该组向量的线性组合的集合，\
且其系数a_1,a_2,…,a_n\in Z^n,即;L = {a_1v_1+a_2v_2+…+a_nv_n,a_n\in Z}}
$$

与格相关的计算性问题

$$
{;;;1.SVP(最短向量问题)：在格L中寻找一个最短的非零向量，即寻找一个非零向量v\in L使得其范数||v||最小。
}
\
{2.CVP(在格中寻找与指定非格向量最为接近的向量)：对于一个不在格中的向量w,寻找一个向量v\in L使得\
||w-v||最小}
$$

LLL算法

可以求解SVP问题
$$
输入一组格的基b_1,b_2,…,b_n \in Z^n进行下列计算\
{for;i=2;to;n;do}\
\qquad\qquad for;j=i-1;to;do\
\qquad\qquad\qquad\qquad\qquad\qquad\qquad
b_i = b_i-c_i,_jb_j ;（c_i,_j=[\frac{\langle b_i,b^*_j\rangle}{\langle b^*_j,b^*_j\rangle}]）\
{而后进行比对，如果;\delta ||b^*_i||>||\mu _{i+1},ib^*i+b^*{i+1}||\
则交换b_i和b{i+1}的值，并回到第一步。\
最后输出b_1,b_2,…,b_n。}
$$
我的理解就是先对这组基做一个施密特正交化，并记下正交化时向量前的系数，而后对输入的基做一个变幻，从第二个开始每个向量减去前面所有的向量与其对应‘系数’的乘积的和，再看看是否满足所需条件。满足就进行交换而后回到开始再来一遍。