分解大整数为两个素因子乘积的析出算法

The Separation Algorithm of Dividing Large Integer into Two Prime Divisor Product

RSA的算法是基于数论中两个大素数乘积所得整数n和选取满足一定条件的整数e组成公开钥(e,n),RSA的安全性是依据大数整数n分解困难性的。根据RSA公钥加密体制的公开密钥n为两个素数乘积的特性,以及Euclid算法的特点,给出了一种分解n的算法—析出算法,并进行了算法的数学证明、算法设计和相关分析。同时,通过也证明了,在RSA密码体制中构造模n时,其素因子的倍数与n1/2距离过近是不安全的结论。

RSA calculation is based on two divisors product n and 1,which forms the conditional public key（e,n）.The safety of RSA depends on the difficulty of dividing the large integer n.According to the characteristic of public key RSA and Euclid Calculations,this essay presents a decomposing n＇s calculation——Separation Algorithm,and undergoes mathematical proof,design and analysis.At the same time,during the design of module n,it proves unsafe if the integer multiple is too close to n（1/2）.