基于多目标优化遗传算法的Schnorr-Adleman整数分解算法

摘要

Schnorr-Adleman整数分解算法将经典整数分解算法中搜索“分解关系对”这一环节转化为素数格上近似最近向量问题的求解，但近似最近向量问题求解的时间复杂度较高。为更高效地在素数格上搜索分解关系对，设计一种多目标优化遗传算法，用于替代Schnorr-Adleman算法中的近似最短向量问题求解算法。该遗传算法同时考虑格向量与目标向量的距离以及格向量的平滑性指标两个适应度函数，并使用快速非支配排序算法和拥挤度函数对格向量的优先级进行排序。实验结果表明，改进后的算法在60、80比特的整数分解实例上的搜索效率均高于经典的Schnorr-Adleman整数分解算法，说明该算法在提高整数分解效率方面具有一定的优势。

关键词

整数分解 / 格 / 最近向量问题 / 多目标优化 / 快速非支配排序