格上困难问题求解的智能筛选算法及测试

在总结格密码困难问题发展和求解中关键理论与技术的基础上,从渐进最短向量问题(approx-SVP)入手,对比分析了经典格基约减算法的优缺点,重点研究了其求解推进过程中的关键技术和算法性能瓶颈,归纳了进行格基约减进而求解渐进最短向量问题的一般步骤。在经典的格向量假设基础上,提出了格向量智能筛选模型。通过优化向量选择的路径等方法,设计了基于最优路径分布的智能筛选算法、逆向求解智能验证算法和近似最短向量智能筛选算法三种求解最短向量问题(SVP)的算法,测试结果表明算法在求解格上困难问题上有效。