分解RSA模数算法研究

Research on Algorithms for Factoring RSA Modulus

RSA密码系统的安全性是基于大数分解困难问题。文中简要地介绍了目前攻击RSA密码系统的常用大数分解算法。详细阐述了大数分解法二次筛选法(Quadraticsieve,QS)以及它的改进算法MPQS和PPMPQS的理论基础。根据PPMPQS的原理,设计了一种快速寻找PP关系的方法以及分析了算法复杂度,并利用VC6实现了PPMPQS,成功分解了十进制70位的大数。

<Abstrcat>RSA security is based on complex problem of large number factoring, and factorization algorithms that attack RSA system in use are introduced simply. QS and its improved algorithm including MPQS and PPMPQS are depicted in detail. By the principle of PPMPQS, a method finding double large prime relation rapidly in PPMPQS is given and its algorithm complexity is analyzed as well. Using Visual C++, PPMPQS is implemented and 70-digits large number is factored.