格密码教程（六）：高斯二维格规约，解决SVP问题

前文已经指出，优质的基对对于算法结果具有重要影响，而在二维格中寻找最优基的算法大多源自高斯的思路。其核心理念是通过交替从一个基向量中减去另一个基向量的倍数，直至无法进一步优化。
设L⊂R^2是一个二维格，其基向量为v_1和v_2。我们要求满足∥v_1∥<∥v_2∥，若初始时v_1与v_2的长度不符合该条件，则应交换两者的位置。接下来尝试通过减去v_1的倍数来使v_2更短。如果允许任意倍数的减法操作，则可以用以下向量替代原来的v_2：
v_2* = v_2 - (v_1·v_2 / ∥v_1∥²) v_1
由此得到的新向量v_2*与原向量v_1正交（上述过程即为施密特正交化方法），而该向量表示的是在与v_1垂直的方向上对原向量v_2进行投影的结果，如图所示：

这显然仅是一种理想化的处理方式，因为所获得的向量v2∗不太可能属于格LL。实际上，仅允许从v2中减去v1的整数倍。因此，我们采用以下方式对v2进行替换：

v2−mv1,m=⌊v1⋅v2∥v1∥2⌉
若替换后的向量v2长度仍大于原向量v1，则终止该过程。否则，将v1与v2交换位置，并重复上述操作。高斯证