Editing Rabin cryptosystem (section)

===Decryption===
The message <math>m</math> can be recovered from the ciphertext <math>c</math> by taking its square root modulo <math>n</math> as follows.

# Compute the square root of <math>c</math> modulo <math>p</math> and <math>q</math> using these formulas:
#: <math>\begin{align}
  m_p &= c^{\frac{1}{4}(p+1)} \bmod{p} \\
  m_q &= c^{\frac{1}{4}(q+1)} \bmod{q}
\end{align}</math>
# Use the [[extended Euclidean algorithm]] to find <math>y_p</math> and <math>y_q</math> such that <math>y_p \cdot p + y_q \cdot q = 1</math>. 
# Use the [[Chinese remainder theorem]] to find the four square roots of <math>c</math> modulo <math>n</math>: 
#: <math>\begin{align}
   r_1 &= \left( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p \right) \bmod{n} \\
   r_2 &= n - r_1  \\
   r_3 &= \left( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p \right) \bmod{n} \\
   r_4 &= n - r_3 
\end{align}</math>

One of these four values is the original plaintext <math>m</math>, although which of the four is the correct one cannot be determined without additional information.

====Computing square roots====
We can show that the formulas in step 1 above actually produce the square roots of <math>c</math> as follows. For the first formula, we want to prove that <math>m_p^2 \equiv c \bmod{p}</math>. Since <math>p \equiv 3 \bmod{4},</math> the exponent <math display="inline">\frac{1}{4}(p+1)</math> is an integer. The proof is trivial if <math>c \equiv 0 \bmod{p}</math>, so we may assume that <math>p</math> does not divide <math>c</math>. Note that <math>c \equiv m^2 \bmod{pq}</math> implies that <math>c \equiv m^2 \bmod{p}</math>, so c is a [[quadratic residue]] modulo <math>p</math>. Then
: <math>m_p^2 \equiv c^{\frac{1}{2}(p+1)} \equiv c\cdot c^{\frac{1}{2}(p-1)} \equiv c \cdot 1 \mod p</math>
The last step is justified by [[Euler's criterion]].