Homomorphic-Encryption
Goldwasser-Micali 方案中的解密
參考以下網址：http ://cryptowiki.net/index.php?title=Goldwasser_Micali_cryptosystem
消息的解密基於該位是否為 QRn，但我們如何知道/驗證（數學運算）它是否為 QRn。
好吧，我們知道密文 $ c $ 是二次殘差，則兩者 $ c \bmod p $ 是一個 QR（模 $ p $ ） 和 $ c \bmod q $ 是一個 QR（模 $ q $ ）。而且，我們知道（對於有效的密文） $ c $ Jacobi 為 1，因此如果它不是 QR，則兩者 $ c \bmod p $ 是一個非 QR（形式 $ p $ ） 和 $ c \bmod q $ 是一個非QR（模 $ q $ ).
而且，我們有私鑰，所以我們可以有 $ p $ . 所以，一種簡單的解密方法 $ c $ 是先評估 $ c \bmod p $ ，然後檢查是否為二維碼；例如，檢查的值 $ (c \bmod p)^{(p-1)/2} \mod p $ ; 如果它評估為 1，那麼 $ c $ 是一個 QR（所以明文是 0）；如果它評估為 $ p-1 $ ， 然後 $ c $ 不是 QR（所以明文是 1）。