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).