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

Schnorr-Adleman Integer Factoring Algorithm with Multi-Objective Optimization Genetic Algorithm

作　　者：栾鸾 顾纯祥[1,2] 郑永辉 LUAN Luan;GU Chunxiang;ZHENG Yonghui(Information Engineering University,Zhengzhou 450001,China;Henan Key Laboratory of Network Cryptography Technology,Zhengzhou 450001,China)

机构地区：[1]信息工程大学,河南郑州450001 [2]河南省网络密码技术重点实验室,河南郑州450001

出　　处：《信息工程大学学报》2025年第2期217-223,共7页Journal of Information Engineering University

摘　　要：Schnorr-Adleman整数分解算法将经典整数分解算法中搜索“分解关系对”这一环节转化为素数格上近似最近向量问题的求解,但近似最近向量问题求解的时间复杂度较高。为更高效地在素数格上搜索分解关系对,设计一种多目标优化遗传算法,用于替代Schnorr-Adleman算法中的近似最短向量问题求解算法。该遗传算法同时考虑格向量与目标向量的距离以及格向量的平滑性指标两个适应度函数,并使用快速非支配排序算法和拥挤度函数对格向量的优先级进行排序。实验结果表明,改进后的算法在60、80比特的整数分解实例上的搜索效率均高于经典的Schnorr-Adleman整数分解算法,说明该算法在提高整数分解效率方面具有一定的优势。The Schnorr-Adleman integer factoring algorithm factorizes a large integer by converting the sub-algorithm of searching for decomposition relations in classical integer factorization to solving the approximate closest vector problem on prime lattices,which has a high time complexity.To search for decomposition relations more efficiently on prime lattices,a multi-objective optimization genetic algorithm is designed to replace the procedure of solving the approximate closest vector problem.Both the distance between lattice vector and target vector and the smoothness metric of lattice vector are taken into consideration.The fast non-dominated sorting algorithm and crowding distance function are applied to rank the candidate lattice vectors.Experimental results demonstrate that the improved algorithm outperforms the classical Schnorr-Adleman algorithm in factoring 60-bit and 80-bit integers,indicating that the algorithm possesses certain advantages in improving the efficiency of integer factorization.

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

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]