GM(Goldwasser-Micali)加密算法

GM（Goldwasser - Micali）機率公鑰加密算法，其基于二次剩餘難以複合困難性問題

具體過程：

 密鑰産生：

1. 大素數p，q，求出N=p*q
2. 任取R，滿足

   

     （J（）雅可比符号）
3. PK（R ,N）,SK （p，q）

加密：

       1. B将明文轉化為二進制數字M=(m1,m2,m3… mk) ∈{0,1}

       2. 對于每一個mi，都對應選取一個xi ∈{1，N-1}   

                                                            若mi=1 ci= 

                                                             若mi=0 ci=

      3.  C ={c1,c2,c3…ck} 将這個C發給A

解密：

       對于每一個ci 都求

與

與

，若都=1,mi=0 ，若都=-1,mi=1

       最終得到M

具體示範（點選進入全屏）：

注：示範中任選R滿足的是

 是負1