在1996年，Ajtai教授在格上问题的困难性基础上给出了一个具有里程碑意义的重要结论。Ajtai教授提出了基于格上难题构造密码方案的可能性。Ajtai教授指出，某一类格上的一些问题的平均难度就等价于格上一类NP问题的难度。

本文首先简要地介绍了格的一些基本概念和相关性质。在18世纪后叶，Lagrange、Gauss和Minkowski提出格并对其进行研究。而到目前，格已经成为了一个在计算机科学领域中活跃的研究分支。格被用来解决有限多变量的线性规划问题,整数上的多项式因式分解, 低密度子集和问题, 许多的密码学问题。上述应用详见文献[1-11]。

格是一组在 维空间中具有周期性结构的点。由于格是一种线性的结构，其上的运算大多都是线性的运算，所以运算效率很高。并且格上的许多问题的困难性已经得到了证明，所以基于格的一些困难性问题来构造的公钥密码体制的安全性也能得到保障。目前大部分的公钥密码体制难以具备的这些优良的特性。近年以来，鉴于上述特性，基于格的一些困难性问题来构造不仅运算速度快，而且安全性能也高的公钥密码体制是国内外密码学研究的一大热点。 

在格理论研究中，格基约简算法是一个极其重要的课题，同时格基约简算法也是密码设计和密码分析中的重要手段。LLL格基约简算法能够较好地解决维数较低的格中的SVP问题和CVP问题，但是随着格的维数的增高，LLL格基约简算法也无法高速高效地解决SVP问题和CVP问题。而许多的基于格理论的密码系统的安全性都依赖于LLL格基约简算法以及其他格基约简算法是否能够高效地解决近似SVP问题和近似CVP问题。也就是说，如果一个基于格理论的密码系统的安全性假设最终能够归约到解决近似SVP问题和近似CVP问题上，那么该密码系统是安全的。因此对格基约简算法的研究是非常有必要的。

二、格的基本概念和相关性质文献综述

我们先来介绍一些格的基本概念和相关性质。

定义1：假设给定 个线性无关的向量 ，那么由这组向量所生成的格被定义为：

 ，其中 称为这个格的基。称这个格的秩为 ，维度为 。如果我们把 写成矩阵 ，其中 为 的列向量，那么这个格可以重新定义为：

 。对于一个向量空间 来说，任意属于该向量空间的 个线性无关向量都能作为该向量空间的一组基。然而对于格来说，由于格是一组在 维空间中具有周期性结构的点，所以情况并不是和向量空间完全对应的。特别的，我们有如下定义和定理：

定义2：我们称一个方阵 为幺模矩阵（unimodular matrix），如果该方阵使得下面的等式成立：