摘要： RSA的安全性是依据大整数分解的困难性而设计的。在RSA的密码分析中，根据RSA公钥加密体制中的公开密钥n为2个大素数乘积的特性，针对形如n=pq(其中，p、q为大素数)的大整数n分解，提出一种分解n的判定算法，并对n的素因子特征与该算法的有效性关系进行分析。经过数学证明和相应算法设计证实，该算法的复杂度低于O(plogn)。

关键词: RSA密码分析, 因式分解, 公钥加密, 复杂度

Abstract: The security of RSA is designed based on the difficulty of large integer decomposition. In the RSA cryptanalysis, according to RSA public key encryption characteristics that the public key n as the product of two large prime numbers, contrary to the form n=pq(in which p, q as large prime numbers) of the large integer n decomposition. A determine algorithm of large integer decomposition on RSA cryptanalysis is given. The decomposition algorithm is proved by mathematical method, the corresponding algorithm design is given, the complexity of the algorithm is made below O(plogn), n prime factor characteristics and the relationship between the effectiveness of the decomposition, as well as RSA safety impacts are analyzed.

Key words: RSA cryptanalysis, factorization, public-key encryption, complexity

中图分类号: 

• TP309