一种格上SVP问题求解的快速分块筛法

摘要

针对现有筛法在通过向量约减构造短向量列表过程中消耗大量时间的问题,基于降维思想,提出一种新型的分块筛法。通过对原始格基分块对应生成多个低维子格,分别在子格上做筛法,获得子格短向量列表;将在子格中得到的短向量列表作为原始格上筛法的初始向量列表,能够较好地提高约化效率,从而更快找到原始格上的最短向量。分块筛技术在对新向量的约减速度与效果上优势更明显,实验数据表明分块筛在运行时间上可以达到平均7.1%的提高。