Rabin加密解密算法
取两个大素数p和q，n=pq
选择这样的pq可以方便简化计算
加密：
为明文空间，选择 
为某一明文，加密公式为 
. 例子：p=7，q=11，n=77，P={0，...，76}，当m=20时，密文c=400 % 77 = 15
解密：
当n无法分解时，我们是无法计算的，还是刚才的例子，我们假设已经用某种方法得到了n=pq，即77=7*11
已知n=77，77=7*11，明文c=15，求密文m
先计算在同余意义下的平方根
当 时，更方便计算，公式为：
时，更方便计算，公式为： 
. 计算得到： 
， 
.
， . 然后，根据扩展欧几里得算法，求得： 
and 
，使得其满足： 
and ，使得其满足： 算得： 
， 
.
， . 根据中国剩余定理，最后的明文空间为：
代入计算得到： 
.
. 小性质： 
= p 或者 = q
= p 或者 = q 
微软公司福利 59人发布
