How to use CRT to compute 4 square roots while decryption in Rabin Cryptosystem I'm reading Rabin Cryptosystem which requires to compute 4 square roots $r, -r, s,- s$ while decryption of cipher text $c$ such that

$$r = (y_p \times p \times m_q + y_q \times q \times m_p) \mod n $$
$$-r = n - r $$
$$s = (y_p \times p \times m_q - y_q \times q \times m_p) \mod n $$
$$-s = n - s $$

$m_p = c^{\frac{1}{4}(p+1)} \mod p; \, \,m_q = c^{\frac{1}{4}(q+1)} \mod q; \, \, y_p \times p + y_q \times q = 1$

I'm not getting, how we can compute $r, -r, s,- s$ using Chinese Remainder Theorem.
As first step to compute the four square roots of $c \pmod N$ one can compute the two square roots $\mod p$ and the two square roots $\mod q$ and then using the Chinese Reminder Theorem combine them to the four square roots $\mod N$ where $N = p \cdot q$.

Let's start computing the square root of ciphertext $c \mod p$.
Usually $p \equiv q \equiv 3 \pmod 4$.
So $m_p = c^{\frac{1}{4}(p+1)} \pmod p$.

Proof: $m_p^2 = c^{2\cdot\frac{1}{4}(p+1)}= c{\frac{1}{2}(p+1)} = c \cdot c^{\frac{p-1}{2}} = c \left( \frac{c}{p}\right) = c \pmod p$, because $c^{\frac{p-1}{2}} = \left( \frac{c}{p}\right) = 1 \pmod p$, where $\left( \frac{c}{p}\right)$ is the Legendre Symbol of $c \mod p$ and $c$ is a square (so the symbol is equal to 1).

Similarly: $m_q = c^{\frac{1}{4}(q+1)} \pmod q$.

Now you have the two square roots modulo the two primes numbers $(m_p, m_q, -m_p = p-m_p, -m_q=q-m_q)$.

Consider now the system:
$$\left\{ \begin{eqnarray}
m = m_p \pmod p \\
m = m_q \pmod q
\end{eqnarray}
\right. $$
Using the extended Euclide algorithm you know that:
$p\cdot y_p + q\cdot y_q = 1$ because $\gcd(p,q)=1$.
So multiplying by $m$:
$m\cdot p\cdot y_p + m\cdot q\cdot y_q = m$.

look at the equality $\mod p$:
$$m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m \pmod p$$
but you know that $m = m_p \pmod p$ and $m = m_q \pmod q$so:
$$m_q\cdot p\cdot y_p + m_p \cdot q\cdot y_q = m\cdot p\cdot y_p + m \cdot q\cdot y_q = m \cdot 0 + m \cdot 1 = m\pmod p$$.

Combining the two possibilities for the square root $\mod p$ with the two possbilities $\mod q$ you'll find the four results you listed.