Editing Rabin cryptosystem (section)

===Example===
As an example, take <math>p = 7</math> and <math>q = 11</math>, then <math>n=77</math>. Take <math>m = 20</math> as our plaintext. The ciphertext is thus 
<math>c = m^2 \bmod{n} = 400 \bmod{77} = 15</math>.

Decryption proceeds as follows:
# Compute <math>m_p = c^{\frac{1}{4}(p+1)} \bmod{p} = 15^2 \bmod{7} = 1</math> and <math>m_q = c^{\frac{1}{4}(q+1)} \bmod{q} = 15^3 \bmod{11} = 9</math>. 
# Use the extended Euclidean algorithm to compute <math>y_p = -3</math> and <math>y_q = 2</math>. We can confirm that <math>y_p \cdot p + y_q \cdot q =  (-3 \cdot 7) + (2 \cdot 11) = 1</math>.
# Compute the four plaintext candidates:
#: <math>\begin{align}
  r_1 &= (-3 \cdot 7 \cdot 9 + 2 \cdot 11 \cdot 1) \bmod{77} = 64 \\
  r_2 &= 77 - 64 = 13 \\
  r_3 &= (-3 \cdot 7 \cdot 9 - 2 \cdot 11 \cdot 1) \bmod{77} = \mathbf{20} \\
  r_4 &= 77 - 20 = 57
\end{align}</math>

and we see that <math>r_3</math> is the desired plaintext. Note that all four candidates are square roots of 15 mod 77. That is, for each candidate, <math>r_i^2 \bmod{77} = 15</math>, so each <math>r_i</math> encrypts to the same value, 15.