子格筛法的两种优化方法

摘要：

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

关键词：格、子格筛法、最短向量问题、自由维数、过滤器

所属期刊栏目：10

分类号：TP309.7(计算技术、计算机技术)

资助基金：国家自然科学基金62032009

在线出版日期：2023-07-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：476-490