RSA密码分析中分解大整数的判定算法

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

Determine Algorithm of Large Integer Decomposition on RSA Cryptanalysis

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.