计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (25): 105-108.DOI: 10.3778/j.issn.1002-8331.2010.25.031

• 网络、通信、安全 • 上一篇    下一篇

一种用于大整数因数分解的多相位粒子群算法

张淑梅1,宋维堂1,宋万里2   

  1. 1.南京交通职业技术学院,南京 211188
    2.河海大学,南京 211188
  • 收稿日期:2010-04-20 修回日期:2010-06-09 出版日期:2010-09-01 发布日期:2010-09-01
  • 通讯作者: 张淑梅

Discussion on Mantissa-multi-phase particle swarm optimization applied to large integer factorization problem

ZHANG Shu-mei1,SONG Wei-tang1,SONG Wan-li2   

  1. 1.Nanjing Communications Institute of Technology,Nanjing 211188,China
    2.Hohai University,Nanjing 211188,China
  • Received:2010-04-20 Revised:2010-06-09 Online:2010-09-01 Published:2010-09-01
  • Contact: ZHANG Shu-mei

摘要: 如果大整数N的两个因数pq满足p=xp×D+ypq=xq×D+yqD>yp×yq约束,那么该大整数N将有可能被轻易分解。因此,根据该约束及相关定理,提出了一种用于求解大整数因数分解问题(IFP)的尾数多相位粒子群搜索算法,MMPPSO。数值实验证明,MMPPSO算法对IFP具有良好的求解能力。同时,建议依赖于大整数N分解问题的密码系统做上述约束条件测试,从而保证密钥和系统的安全性。

关键词: RSA, 强素数, 大整数因数分解问题(IFP), 粒子群优化算法(PSO)

Abstract: If the two factors p and q of N(a large integer) satisfy the constraint of p=xp×D+ypq=xq×D+yq and D>yp×yq,then N can be easily factorized.Therefore,the Mantissa-Multi-Phase Particle Swarm Optimization(MMPPSO) applied to large Integer Factorization Problem(IFP) is proposed on the basis of the constraint and some related theorems.Data experiment shows that MMPPSO is excellent in solving IFP.Meanwhile,it is suggested that the cryptosystem relied on large IFP of N be tested on the above constrained conditions,so as to guarantee the safety of encryption key and the system.

Key words: RSA, strong prime numbers, Integer Factorization Problem(IFP), Particle Swarm Optimization(PSO)

中图分类号: