终于有时间好好学学格论的基础部分，做一个笔记。 本文目前重点介绍格基约化的LLL算法。其他部分可能另外进行更新。
格
定义
欧几里得空间上上一个离散加法子群称为格\(L\)。其可由一组格基的整系数线性组合生成。
事实上，一个格是同一组基下的线性空间的一个特殊子集。
通常来说，当我们需要解决格中最短向量问题（SVP）、最近向量问题（CVP），及其近似问题（apprSVP、apprCVP）时，我们希望有一组尽可能正交的基，并称基的正交程度为基的质量。而LLL算法是优化基的质量的一个可行方法。
方便起见（同时基于其基本应用），我们局限于讨论维数与基的数量相同的格。
Hadamard比率
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格基约化算法
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条件。
我们将先阐述两个条件的内容，然后介绍算法过程中维护两个条件成立的机制
目标条件
Size条件
对约化后的格基\((\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\]
Lovász条件
此条件为一个有序性条件，对约化后的格基\((\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,0<k\leq n\] 其中\(\mu_{i,j}\)的定义同Size条件中所述
算法过程
LLL的约化过程，是先约化前\(k\)个基，然后拓展到\(k+1\)个基，最终完成全部\(n\)个基的约化过程。
约化的主要思想是在对基进行整系数下近似的Schmidt正交化过程中，保证正在操作的向量满足Size条件；然后对Lovász条件进行验证，直至Lovász条件被满足；否则，将会进行下一轮的迭代。
如果加入第\(k\)条基后导致Lovász条件不再满足，那么我们可以改变基的排列顺序。这一操作不会使前\(k\)条基满足Lovász条件，但它可以使得有一个\(j<k\)，使前\(j\)条基包含新加入的基，并且满足Lovász条件，使得下一轮迭代可以从\(j\)处重新开始。具体的操作与证明将在下文针对伪代码具体分析。
算法过程本身比较简单，此处仿照[1]给出一份伪代码。
Input {v[1],v[2],...,v[n]} //输入n条向量作为初始格基
Set k=2
Loop while k<=n:
Set {v*[1],v*[2],...,v*[k]} = Gram_Schmidt({v[1],v[2],...,v[n]})
Loop for j from k-1 downto 1:
set v[k] = v[k] - μ[k,j]*v[j] //Size条件
end Loop
If dot(v*[k],v*[k])>=(0.75-μ[k,k-1]*μ[k,k-1])*dot(v*[k-1],v*[k-1]) : //Lovász条件
Set k=k+1
else : //不满足Lovász条件时基顺序的维护
Swap(v[k-1],v[k])//与相邻基交换，在下一个迭代过程继续与位置更小的基进行比较
k = max(k-1,2)
end If
end Loop接下来进行算法细节的讨论
Size条件的保证
以下两行代码保证\(k\)轮操作后前\(k\)组基满足Size条件。
Loop for j from k-1 downto 1:
set v[k] = v[k] - round(μ[k,j])*v[j] //Size条件
end Loop只需证明进行进行\(j\)次操作后，对所有\(i\leq j\)，有\(\mu_{k,i}\leq\frac12\)，这可以归纳证明，并直接以该命题作为归纳假设。 对\(j=j_0<k\)，设\(v_1,v_2,\cdots,v_n\)为操作前的向量，\(\mu'\)为操作后的\(\mu\)，则在操作后，考虑\(i=j_0\)的情况 \[\mu_{k,j_0}'=\frac{\left(v_{k}-\lfloor\mu_{k,j_0}+0.5\rfloor v_{j_0} \right) \cdot v_{j_0}^*}{\Vert v_{j_0}^*\Vert^2}=\mu_{k,j_0}-\lfloor\mu_{k,j_0}+0.5\rfloor\in [-0.5,0.5]\]
这同时证明了\(j=k-1\)的归纳初始条件。 对\(j\leq j_0+1\)，Size条件成立时，考虑\(j=j_0\)的情况。任取一个\(i>j\):
\[ \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]\]
$$$$
有限时间内算法终止的保证[2]
基本证明思路在于，构造一个参数，随迭代变化，然后证明其变化次数是有限的。
考虑 \[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条件时，对格基顺序的交换操作。
If not Lovász:
Swap(v[k-1],v[k])
k = max(k-1,2)
end If由格的性质，我们知道格中存在非零的最短向量，设最短向量长度为\(s>0\), 从而有：\[D\geq s^{\frac{n(n+1)}{2}}>0\] 而对于初始的格基，初始的\(D\)是一个确定的常数\(D=D_0<+\infty\)。 如果我们能够证明交换前的\(D\)，与交换后的\(D'\)满足关系注3：\(D'\leq \frac{3}{4}D\)，那么交换操作进行的轮数就有上限:\[L=\log_{\frac43}\left(D_0s^{-\frac{1}{2}n(n+1)}\right)\] 这样就可以说明算法一定在有限次运算后结束注4
接下来我们对交换前后的\(D\)满足的关系\(D'\leq \frac{3}{4}D\)进行证明。记交换前的正交基为\(v_k^*\)，\(D\)为\(D^*\)；交换后的正交基为\(v_k^{**}\), \(D\)为\(D^{**}\)
交换操作只影响被交换的两个位置对应正交基的模的大小，于是我们不妨直接讨论二维基\(v_1\)与\(v_2\)交换的情形。在这种情况下，交换前我们有： \[\boldsymbol{v_1^*}=\boldsymbol{v_1},\ \boldsymbol{v_2^*}=\boldsymbol{v_2}-\frac{\boldsymbol{v_2}\cdot \boldsymbol{v_1}}{\Vert\boldsymbol{v_1}\Vert^2}\boldsymbol{v_1}\]\[D^*=\Vert\boldsymbol{v_1^*}\Vert^2\Vert\boldsymbol{v_2^*}\Vert\] 交换后： \[\boldsymbol{v_1^{**}}=\boldsymbol{v_2},\ \boldsymbol{v_2^{**}}=\boldsymbol{v_1}-\frac{\boldsymbol{v_2}\cdot \boldsymbol{v_1}}{\Vert\boldsymbol{v_2}\Vert^2}\boldsymbol{v_2}\]\[D^{**}=\Vert\boldsymbol{v_1^{**}}\Vert^2\Vert\boldsymbol{v_2^{**}}\Vert\]与交换前比较有： \[\boldsymbol{v_1^{**}}=\boldsymbol{v_2^*}+\mu_{2,1}^2\boldsymbol{v_1},\ \Vert\boldsymbol{v_2^{**}}\Vert\Vert\boldsymbol{v_1^{**}}\Vert=\Vert\boldsymbol{v_2^{*}}\Vert\Vert\boldsymbol{v_1^{*}}\Vert\]
此时代入Lovász条件并结合正交性：\[\Vert\boldsymbol{v_2^*}\Vert\geq\left(\frac{3}{4}-\mu_{2,1}^2\right)\Vert \boldsymbol{v_{1}^{*}}\Vert\Rightarrow\Vert\boldsymbol{v_2^*}+\mu_{2,1}^2\boldsymbol{v_{1}^{*}}\Vert\geq\frac{3}{4}\Vert \boldsymbol{v_{1}^{*}}\Vert\Rightarrow\Vert\boldsymbol{v_1^{**}}\Vert\geq\frac{3}{4}\Vert \boldsymbol{v_{1}^{*}}\Vert\] 从而得到 \[ \frac{D^*}{D^{**}} = \frac{\boldsymbol{v_1^{**}}}{\boldsymbol{v_1^*}}\geq\frac34\Rightarrow D^{**} \leq \frac{3}{4} D^*\] 这可以得到算法必定在有限次操作后结束。
注3：可以从证明的过程中看出，在\((0.25,1)\)范围内改变程序中\(\frac{3}{4}\)的值，仍能得到算法收敛的结论，但会造成最终得到的格基有所不同
注4：仅仅证明了算法在有限次操作后结束，具体复杂度下次一定
Lovász条件的保证
我们在每个循环都会对Lovász条件进行校验
If dot(v*[k],v*[k])>=(0.75-μ[k,k-1]*μ[k,k-1])*dot(v*[k-1],v*[k-1]) : //Lovász条件
Set k=k+1
end If可以看出，每次\(k\)变大的过程均表明Lovász条件在\(k\)处成立，那么只要算法可以结束（这已经证毕），Lovász条件就一定满足。从而这一算法能得到一组满足Lovász条件
算法分析
本节讨论LLL算法两个主要条件对约化格基的意义，即这两个形式简洁的条件是如何优化格基的。
但是我没力气写了，等我活过期中再来补。
一些吐槽
国内讲格论的书，仿佛独有周福才这一本。对格的一些估计式，和数学本质相关的东西，看起来还是比网上找博文全面一些。然而重点看的LLL算法，自己试图做补充证明，才发现它上面的代码也是错的（近似正交化部分需要倒序迭代才能满足Size条件），证明也有不小的问题。虽然找错误蛮开心的，不过还是让人走了不少弯路（最后终于想起来去看原始论文把算法终止性补了一下）。
参考资料
[1] 周福才, 徐剑. 格理论与密码学. 科学出版社
[2] Lenstra, A.K., Lenstra, H.W. & Lovász, L. Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982). https://doi.org/10.1007/BF01457454
更新记录
2021.4.17: 完成主体内容
2022.2.19: 修正了一部分不准确的定性说明