平均情况下BKZ算法的启发式分析

作为使用最广泛的格基约化算法,BKZ算法是攻击格密码体制或者评估其安全性最重要的工具之一.然而,BKZ算法在实际中的行为预测是一个著名的难题.Hanrot等人基于动力系统方法在2011年首次给出BKZ算法的一个分析结果.他们发现在BKZ算法运行过程中只需多项式次调用SVP子程序即可保证输出约化基的质量.最近,Li和Nguyen改进了Hanrot等人的分析结果,给出BKZ算法运行时间和输出质量更好的上界.然而,关于BKZ算法的理论分析仍有一些问题需要被解决:(1)在BKZ算法的动力学分析中,调用LLL算法对格基产生的影响难以被合理地解释;(2)已有关于BKZ算法的分析结果都是在最坏情况下得到的,与其在实际中的表现存在明显偏差.本文的主要贡献在于基于高斯启发式和动力系统方法给出BKZ算法在平均情况下的一个启发式分析.在本文给出的分析中,上述LLL算法产生的影响可以通过几何级数假设被合理地解释.本文最终得到的分析结果不仅在理论上具有更好的上界,而且可以更准确地估计BKZ算法实际输出约化基的质量.实验结果可以验证上述结论.

分布式人工蜂群免疫算法求解函数优化问题

为了克服人工蜂群算法由于开发能力较弱而导致收敛速度慢、搜索精度不高等缺点,结合子蜂群思想和免疫克隆选择算法,提出一种基于分布式精英进化模型的人工蜂群免疫算法.首先对外层子蜂群进行启发式快速人工蜂群操作以提高收敛速度;然后对内层精英蜂群进行免疫克隆选择操作,进一步提高了算法的收敛精度和全局搜索能力.仿真结果表明了该算法在求解函数优化问题上的有效性和优越性.