算法优化的第一部是找出一个算法中最为耗时的部分并进行针对性的优化。在BKZ 2.0中,作者发现BKZ算法最耗时的部分是当块较大时的枚举子算法,所以作者从以下三个角度对枚举子算法进行了优化。首先是剪枝,对递归的每一层进行更为细致的剪枝,保证总体程序的高成功概率;其次是预处理,原算法中使用LLL算法进行预处理,但枚举后可能产生约化程度更高的约化基,作者使用BKZ预处理代替LLL预处理;最后是对枚举半径的优化,原算法的枚举半径使用现有的正交基,作者结合高斯估计,减小了初始枚举半径,从而降低枚举时间。
将枚举子算法进行改进后,BKZ2.0算法能够支持更大分块,更高维格的BKZ格基约化,并且作者提出的模拟算法可以在算力受限的情况下得到算法的预期结果和运行时间,在理论和实践方面都有贡献,除此之外,模拟算法还可以改进格上困难问题的安全性估计。
该实验结果为模拟算法与实际算法的对比,可以看出该模拟算法可以较好的模拟BKZ算法。