18世纪以来，格理论作为数的几何的研究核心，一直受到数学家们的广泛关注;而近二十年来，随着基于格的公钥密码体制的提出，格也逐渐成为计算机学界和密码学界感兴趣的课题。于是对格理论的研究被赋予了新的时代涵义;同时，对格上最短向量问题(SVP)的复杂性研究也非常重要，因为它决定了基于格的公钥密码体制的安全性。　　本文从格理论入手，研究探讨了随机满秩整格这一对象。用整矩阵的Hermite标准型对应整格，通过一类多个变量的幂乘积求和估计，讨论了随机满秩整格的统计性质，进而给出了随机满秩整格和随机简单整格的生成算法。　　本文第二项工作是求解低维循环生成格（一类特殊的格）上的SVP。充分利用SVP解中蕴含的信息，证明了SVP解在其循环格基下的整系数有很小的上界，然后通过穷举所有可能的SVP解，归纳出了十分简单清晰的结果。该结果表明不同于一般格上的SVP，低维循环生成格上的SVP是极易求解的。　　本文第三项工作是给出了随机子集和问题到任意lp范数SVP的归约。Coster等人证明了l2范数SVP预言机能用来解决几乎所有密度小于0.9408的随机子集和问题实例，我们将这个结果推广到lp范数。通过对lp范数球中整点个数的有效估计，证明对正整数p，lp范数SVP预言机能用来解决几乎所有密度小于δp的随机子集和问题实例（其中δ1=0.5761，δp≈2p+o（p)对p≥2）。有趣的是，p≥3时，lp范数SVP预言机能用来解决密度为1的随机子集和问题实例（被认为是最困难的实例）。　　本文最后讨论了SVP不同版本间的归约，包括搜索SVP到优化SVP的新归约和搜索SVPγ到优化SVPγ的改进归约。运用p进展开的组合技巧，构造了搜索SVP到优化SVP的新归约，其调用优化SVP预言机的次数从多项式次降到了一次（已是最少）。还改进了搜索SVPγ到优化SVPγ的归约，近似因子间的关系从γ=γ1/n(n-1)(n+log2γn)改进到γ=γO(log2n)/n(n-1)(n+log2γn)。