Why, in the Rabin cryptosystem, during decryption, do we get four possibilities instead of two?

Question

The encryption algorithm : c=m^2 modn, should mean that we have two(or one) possibilities for m. Why do we get four squareroots?

Answer 1

For a prime $p$ the congruence $x^2 \equiv a \pmod p$ has either $0$ or $2$ solutions for $a \neq 0$. For example, $3^2 \equiv 2^2 \equiv 4 \pmod 5$, and $2^2 \equiv 5^2 \equiv 4 \pmod 7$. In a hand-wavy way, we can get a solution to both congruences at the same time by choosing one from each. Two solutions and two choices leads to $4$ overall possibilities. (In a less handwavy way, you follow the Chinese Remainder Theorem).

For example, the four square roots of $4$ mod $35$ are $2, 12, 23,$ and $33$. In these, you'll notice a pair congruent to $2 \pmod 5$, a pair congruent to $3 \pmod 5$, a pair congruent to $2 \pmod 7$, and a pair congruent to $5 \pmod 7$ (these are the same as the solutions I mentioned earlier). This is not a fluke, but a byproduct of the Chinese Remainder Theorem in action.