子格筛法的两种优化方法

摘要

子格筛法是求解格上最短向量问题(shortest vector problem,SVP)的一个高效算法,通过在(n-d)维投影子格上调用高斯筛法以求解n维格上的SVP问题,其中d是自由维数.子格筛法的降维思想有效降低了筛法的时间复杂度,缩小了与枚举算法运行效率的差距.本文在简要回顾高斯筛法和子格筛法的算法思想及运行机理的基础上,提出子格筛法的两种优化方法.通过调整高斯筛法的算法参数,改变算法输出包含的信息,增大了子格筛法的自由维数d,从而降低了算法的时间复杂度;在子格筛法最重要的子程序高斯筛法中加入过滤器,在更新列表向量的同时可以更快地完成筛选,从而将高斯筛法的二次搜索过程降低为亚二次搜索过程,节约了算法的运行时间;综合应用上述两种方法优化子格筛法,提出Filteredα-子格筛法.实验数据表明两种优化方法都能有效提升子格筛法的运行效率.在70–86维的随机格上,Filteredα-子格筛法的运行效率相比于初始子格筛法最高提升了约58.8%,平均提高了约41.7%.