概念准备

在说之前，有几个概念需要明确，一个是欧式空间，需要满足三个条件:

这里的$<k1a1+k2a2,β>$是内积，就是k1a11+k2a21….
对于向量a，定义其欧式范数为||a||=$\sqrt{<a,a>}$,其实就是向量长度
另外格还要用到大一学的施密特正交化

格与格基

格：给定n个线性无关的向量b1…bn∈R^m^,则称其整系线性组合构成的集合

为R^m^上的格。我们称$L$的秩为n，$L$的维数为m。我们称上述格的定义中出现的b1….bn为格L的一组基，称为格基.
记B=(b1,…,bn),称B为基矩阵，那么格L可以进一步表示为可以验证L为R^m^的离散加法子群。与向量空间R^m^类似地，格L的基不止一个。事实上，任意一个秩为1的格有两组基，而秩大于等于2的格有无数组基。取格L的任意两组基，一组基矩阵可由另一组基矩阵左乘一个幺模矩阵U得到，U为过渡矩阵。

基本域和体积

称格L的一组格基围成的基本平行体为格L的基本域，其严谨定义如下.
基本域：设L为一个n维的格，且L的一组基为v1,v2….vn,则格L的基本域为

整格

密码学中的运算对象基本都是整数，因此实际应用中往往使用整格，整格有时候也称为整数格.

格基规约

说了这么多，其实格基规约就是
1.输入基向量集合B={b1…bn}，设置m=dim(B),也就是维度
2.施密特正交化

3.规约过程
对于$i<j$,计算:
如果|u{i,j}|>1/2,则更新:

4.检查过程
对于每个i从1到n-1，检查:

如果条件不满足，交换bi和bi+1,并返回步骤2
重复步骤3和4，直到满足条件。最终得到一个规约后的基B^’^={b1^’^,b2^’^…bn^’^}