Determine Algorithm of Large Integer Decomposition on RSA Cryptanalysis
Sun Ke-quan · Jisuanji gongcheng · 2010
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.