前言：

最近做了一个以RSA算法为原型的题，这里对其中涉及到的问题及算法进行一个分析和总结。

RSA算法简介：

RSA算法是一种加密算法，广泛应用于现在的信息加密传输等领域，它的狭义应用流程如下：

现在加如你需要传送某一串信息M(这里简化为数字)给一些人，利用RSA算法加密以后你可以得到一个密文C，然后你将密文C传送给你需要传达的人，而对方有一个密钥D，对方可以比较容易地利用密钥D将密文C解密得到需要的信息M。那么这里为了传输信息的保密，我们就要尽可能保证密文C不会被其它人解密，也就是尽可能无法让旁人得到D的值。下面讲一下该加密的方法：

首先我们找到两个非常大的质数P和Q，使N=P*Q，T=(P-1)*(Q-1)，然后在区间(0~N)之间取一个与T互质的数E，即GCD(E,T)=1，然后我们计算得到D，使得(E*D)%T=1，实际上这里的D也就是E再模T意义下的乘法逆元。

而加密时得到密文的方法就是C=(M^E)%N，由密文得到明文就是M=(C^D)%N;

接着{E，N}作为公钥，每个人都知道，{D，N}作为密钥只有少数人知道。

这里有个小问题，为什么经过解密时得到的M就是原来的M呢？这里做一个小运算(加密时M1，解密得到M2)：

M2=(C^D)%N

=(((M1^E)%N)^D)%N

=((M1^E)^D)%N                                                   //模乘可交换性

=M1^(E*D)%N

=M1^(E*D%phi(N)+phi(N))%N                             //欧拉降幂公式a^b%c=a^(b%phi(c)+phi(c))%c（需要b>phi(c)）

=(M1^(E*D%phi(N))%N)*(M1^phi(N))%N)%N

=M1^((E*D)%((P-1)*(Q-1)))%N                             //欧拉定理–a^phi(p)%p=1（需要a与p互质）

=M1^1%N

=M1

那么显然只要有了D和C，那么很容易便可以得到明文M，而D又由E和T得到，E公开，T由N得到，所以旁人要解密就需要由N得到T，而我们知道N=P*Q，T=(P-1)*(Q-1)，所以要解密就是如何将N分解得到P和Q了。下面对整数分解进行介绍。

Pollard-rho整数因子分解：

（待续…）