# Decryption in Goldwasser-Micali Scheme

Referring to the following URL: http://cryptowiki.net/index.php?title=Goldwasser_Micali_cryptosystem

The decryption of the message is based on wether the bit is a QRn or not, but how do we know/verify (the mathematical operations) if it is a QRn or not.

Well, we know that the ciphertext $$c$$ is a Quadratic Residue, then both $$c \bmod p$$ is a QR (modulo $$p$$) and $$c \bmod q$$ is a QR (modulo $$q$$). And, we know that (for valid ciphertexts) $$c$$ has a Jacobi of 1, and so if it is not a QR, then both $$c \bmod p$$ is a non-QR (modulo $$p$$) and $$c \bmod q$$ is a nonQR (modulo $$q$$).
And, we have the private key, and so we can have the value of $$p$$. So, one simple way to decrypt $$c$$ is to first evaluate $$c \bmod p$$, and then check if it is a QR; for example, check the value of $$(c \bmod p)^{(p-1)/2} \mod p$$; if it evaluates to 1, then $$c$$ is a QR (and so the plaintext is 0); if it evaluates to $$p-1$$, then $$c$$ is not a QR (and so the plaintext is 1).