格简介与LLL格基约化

终于有时间好好学学格论的基础部分，做一个笔记。 本文目前重点介绍格基约化的LLL算法。其他部分可能另外进行更新。

欧几里得空间上上一个离散加法子群称为格\(L\)。其可由一组格基的整系数线性组合生成。

事实上，一个格是同一组基下的线性空间的一个特殊子集。

通常来说，当我们需要解决格中最短向量问题（SVP）、最近向量问题（CVP），及其近似问题（apprSVP、apprCVP）时，我们希望有一组尽可能正交的基，并称基的正交程度为基的质量。而LLL算法是优化基的质量的一个可行方法。

方便起见（同时基于其基本应用），我们局限于讨论维数与基的数量相同的格。

Hadamard比率是描述线性空间中一组基正交程度的参数。对于一组基：\(\beta=(\boldsymbol{v_1'},\boldsymbol{v_2'},\cdots,\boldsymbol{v_n'})\),其Hadamard比率有公式：

\[\mathscr{H}(\beta)=\frac{|\mathrm{det}(\boldsymbol{v_1'},\boldsymbol{v_2'},\cdots,\boldsymbol{v_n'})|}{\Vert\boldsymbol{v_1'}\Vert\Vert\boldsymbol{v_2'}\Vert \cdots \Vert\boldsymbol{v_n'}\Vert}\]

容易发现，当格空间不发生改变的时候，格基的行列式也不会改变。在这一情况下，向量的平均长度，就决定了Hadamard比率的值注1。这一参数越接近于1，表明该基的基向量几何平均长度越短，正交程度越高，基的质量越好。

注1: 从几何的角度理解，既然行列式的值表征超多面体体积，各个向量长度之连乘越接近超多面体的体积，自然表明正交程度更好

格基约化的目的是提高格基的质量。即，经过约化的格基将会拥有更高的正交程度，也就是拥有更高的Hadamard比率。 同时，正交程度越高时,基的长度应该越低。那么一组优质基中，就更有可能包含一个apprSVP的可能解注2。 一种简单的格基约化称为高斯约化算法，只针对二维格基可用，做法与数论中的欧几里得算法相似。 另一个常用的格基约化算法为本文重点讨论的Lenstra-Lenstra-Lovász格基约化算法（LLL格基约化）多项式时间内处理更高维的格基约化问题

注2: apprSVP问题中我们真正关心的是基中最小向量的长度，而Hadamard比率减小只能直接表明基中向量的平均长度减小。

LLL算法约化的过程，实际是尽可能用格基去贴近线性空间的正交基的过程。实际操作中，我们先通过Schmidt正交化获得当前格基对应正交基，然后利用正交基对格基中的向量进行约化。

设格上的一组劣质基\((\boldsymbol{v_1'},\boldsymbol{v_2'},\cdots,\boldsymbol{v_n'})\)，LLL格基约化的结果是一组优质基\((\boldsymbol{v_1},\boldsymbol{v_2},\cdots,\boldsymbol{v_n})\)，其满足Size条件与Lovász条件。

我们将先阐述两个条件的内容，然后介绍算法过程中维护两个条件成立的机制

对约化后的格基\((\boldsymbol{v_1},\boldsymbol{v_2},\cdots,\boldsymbol{v_n})\)，与约化后的格基对应的Schmidt正交基\((\boldsymbol{v_1^*},\boldsymbol{v_2^*},\cdots,\boldsymbol{v_n}^*)\)，那么Size条件可以表示为：

\[\mu_{i,j}=\frac{\boldsymbol{v_i}\cdot\boldsymbol{v_j^*}}{\Vert \boldsymbol{v_j}^* \Vert^2}\in \left[-\frac{1}{2},\frac{1}{2}\right],\ 0< j < i < n\]

此条件为一个有序性条件，对约化后的格基\((\boldsymbol{v_1},\boldsymbol{v_2},\cdots,\boldsymbol{v_n})\)，与约化后的格基对应的Schmidt正交基\((\boldsymbol{v_1^*},\boldsymbol{v_2^*},\cdots,\boldsymbol{v_n}^*)\)，需成立： \[\Vert\boldsymbol{v_k^*}\Vert\geq\left(\frac{3}{4}-\mu_{k,k-1}^2\right)\Vert \boldsymbol{v_{k-1}^{*}}\Vert,0j\):

\[ \mu_{k,i}'=\frac{\left(v_{k}-\lfloor\mu_{k,j}+0.5\rfloor v_j \right) \cdot v_{i}^*}{\Vert v_{1}^*\Vert^2}=\mu_{k,i}-\frac{\lfloor\mu_{k,1}+0.5\rfloor}{\Vert v_{k-1}^*\Vert^2}(v_j\cdot v_i^*)\] 我们考虑Schmidt正交化的过程，可以知道\(v_j\)是前\(j\)条正交基的线性组合，而\(v_i^*\)则与前\(i-1\)条基都正交，从而得到\(v_j\cdot v_i^*=0\)，然后利用归纳假设： \[ \mu_{k,i}'=\mu_{k,i}-\frac{\lfloor\mu_{k,1}+0.5\rfloor}{\Vert v_{k-1}^*\Vert^2}(v_j\cdot v_i^*)=\mu_{k,i}\in [-0.5,0.5]\]

$$$$

基本证明思路在于，构造一个参数，随迭代变化，然后证明其变化次数是有限的。

考虑 \[D=\prod_{k=1}^{n}\prod_{j=1}^{k}\Vert v_{i}^*\Vert=\prod_{k=1}^{n}\Vert v_{k}^*\Vert^{n+1-k}\]

对于维护Size条件的操作，其不会改变格基组对应的Schmidt正交基，从而不会改变\(D\)的值。 于是，能改变\(D\)的值的操作只有不满足Lovász条件时，对格基顺序的交换操作。

由格的性质，我们知道格中存在非零的最短向量，设最短向量长度为\(s>0\), 从而有：\[D\geq s^{\frac{n(n+1)}{2}}>0\] 而对于初始的格基，初始的\(D\)是一个确定的常数\(D=D_0