1.算法步骤：

• 选择两个质数 p , q p,q p,q
• 计算 N = p ∗ q ， ϕ ( N ) = ( p − 1 ) ∗ ( q − 1 ) N=p*q，\phi(N)=(p-1)*(q-1) N=p∗q，ϕ(N)=(p−1)∗(q−1)
• 选择一个与小于 N N N的与 N N N互质的数 e e e，并且求出 e e e在模 ϕ ( N ) \phi(N) ϕ(N)意义下的乘法逆元 x x x
• e作为公钥，x作为私钥
• 加密就是 A e % N = M A^e \% N=M Ae%N=M
• 解密就是 M x % N = A M^x\%N=A Mx%N=A

2.算法证明：
M = A e M=A^e M=Ae
M x = ( A e ) x M^x=(A^e)^x Mx=(Ae)x
e ∗ x ≡ 1 ( m o d ϕ ( N ) ) e*x\equiv1(mod \phi(N)) e∗x≡1(modϕ(N))
A e x ≡ A A^{ex}\equiv A Aex≡A