算法描述    
   随机选择两个大的素数 p、q ，且p ≠ q，计算n = pq、r = (p-1)(q-1)，依欧拉定理，r即为与n互质的素数个数；选择一个小于r的整数e（即加密指数），求得e关于模r的逆元素d（即解密指数），则{n，e}为公钥、{n，d}为私钥；根据模的逆元性质有ed ≡ 1 (mod r)；设m为明文，则加密运算为m^e ≡ c (mod n)， c即为密文；则解密过程 c^d ≡ m (mod n)。
   证明会用到费马小定理，即 若 n 和 m 互质, 则 n^(m-1) ≡ 1 (mod m)（费马小定理的证明需先证明欧拉定理，此处略）。符号≡表示同余，^表示幂，|表示整除，*表示相乘。

算法证明
 第一种证明途径   
   因 ed ≡ 1 (mod (p-1)(q-1))，令 ed = k(p-1)(q-1) + 1，其中 k 是整数
   则 c^d = (m^e)^d = m^(ed) = m^(k(p-1)(q-1)+1)
   1.若 m 不是 p 的倍数，也不是 q 的倍数时，
      则 m^(p-1) ≡ 1 (mod p) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod p)
      m^(q-1) ≡ 1 (mod q) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
      所以 p，q 均能整除 m^(k(p-1)(q-1)) - 1
         => pq | m^(k(p-1)(q-1)) - 1
      即 m^(k(p-1)(q-1)) ≡ 1 (mod pq)   
         => m^(k(p-1)(q-1)+1) ≡ m (mod n)   

   2.若 m 是 p 的倍数，但不是 q 的倍数时，
      则 m^(q-1) ≡ 1 (mod q) (费马小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
         => m^(k(p-1)(q-1)+1) ≡ m (mod q)
      因 p | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod p)
         => m^(k(p-1)(q-1)+1) ≡ m (mod p)
      故 m^(k(p-1)(q-1)+1) ≡ m (mod pq) 
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

   3.若a是 q 的倍数，但不是 p 的倍数时，证明同上

   4.若m同时是p和q的倍数时，
      则 pq | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod pq)
         => m^(k(p-1)(q-1)+1) ≡ m (mod pq)
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

 第二种证明途径
   ed ≡ 1 (mod (p-1)(q-1))
       => ed ≡ 1 (mod (p-1))，ed ≡ 1 (mod (q-1))
   令ed = k(p-1) + 1，k > 1，则解密过程 
      c^d = m^e^d = m^(ed) = m^[k(p-1)+1] = m * m^[k(p-1)]
   因p为质数，依费马小定理有   
      m^(p-1) ≡ 1 (mod p)
       => m^[k(p-1)] ≡ 1 (mod p)
       => m * m^[k(p-1)] ≡ m (mod p)  
   即 c^d ≡ m (mod p) 
   同理可证c^d ≡ m (mod q)
   因p，q都为质数，所以c^d ≡ m (mod pq)，即 c^d ≡ m (mod n)