在这个数据爆炸的年代,信息安全问题日益突出,因而密码学在信息化的时代扮演着越来越重要的角色。由于格密码具有无可比拟的低能耗优势和抗量子攻击的特性,使得格密码学得到了广泛的关注。格基规约相关算法是格密码学的重要组成部分。格基规约相关算法主要针对最短向量问题(SVP)、最近向量问题(CVP)这两种困难问题的求解,经典的格算法主要有LLL、BKZ、GaussSieve、NV等。格基规约相关算法在计算机代数、整数规划以及密码学等领域具有广泛的应用。本篇论文主要从优化求解SVP随机筛选算法的时间复杂度、用局部半径代替全局半径的策略来优化求解CVP问题的球译码算法来阐述,具体内容如下:(一)目前,解决SVP问题的筛选算法的最优空间复杂度是20.2075n+o(n)(n是格的维数)。在高维格的情况下,筛选算法对内存空间的高需求成为了它和枚举算法竞争的绊脚石。Filtered triple sieving algorithm算法打破了这一瓶颈,首次把筛选算法的空间复杂度降低到20.1887n+o(n)。但是该算法的时间复杂度却高达20.4812n+o(n)。为了优化Filtered triple sieving algorithm算法的时间复杂度,我们提出了一种新的随机筛选算法FT-HashSieve,它可以在时间20.4098n+o(n)内解决SVP问题,同时保持空间复杂在20.1887n+o(n)。我们同时用FT-HashSieve算法的适当变形解决CVP问题,截止到目前,该方法是解决CVP问题的算法当中空间复杂度最低的算法。(二)球译码算法(SDA)是解决CVP问题的有效方法之一,有效的剪枝技术可以降低球译码算法(SDA)的时间复杂度。球译码算法中的半径R决定了搜索空间的大小,我们首次提出了用动态半径代替全局搜索半径的策略。我们算法的核心思想是牺牲相对较小的求解精度换取较大时间复杂度的降低。