# Rabin cryptosystem - How many solutions?

If in Rabin cryptosystem we have $n = p \cdot q$ where $p$ and $q$ is prime we have four solutions (roots) - exist four solution of $x^2 \equiv b \pmod{n}$.

However, when we have:

$n = p \cdot q \cdot r$

where $p$ and $q$ and $r$ is prime or:

$n = p \cdot q \cdot r \cdot z$

where $p$ and $q$ and $r$ and $z$ is prime

How much will we have solutions?

will they be $2^k$? where $k$ is the number of prime numbers?

How much will we have solutions?

Assuming:

• $p, q, r, ..., z$ are distinct odd primes

• $b$ is relatively prime to $n$

• There exists at least one solution

Then, yes, there will be precisely $2^k$ solutions.

This is straight-forward to show; as we know there exists a solution $x_0$ such that $x_0^2 = b \pmod n$, then this implies that:

$$x_0^2 = b \pmod p$$

$$x_0^2 = b \pmod q$$

...

$$x_0^2 = b \pmod z$$

We know that the first equation has two solutions modulo $p$; $x_0$ and $-x_0$ (as $b$ is relatively prime to $p$, and hence $x_0 \ne 0 \pmod p$, and $p$ is odd, so $x_0 \ne -x_0 \pmod p$). We also know there cannot be a third (as that would imply a nontrivial factorization of $p$, contradicting the assumption that $p$ was prime).

Similarly, the rest of the equations have 2 solutions; hence using the Chinese Remainder Theorem, there are $2^k$ was to recombine these solutions into an $x$ value that satisfies all these equations (and hence the original one).

We can also show that any value of $x$ not in the set of $2^k$ will not satisfy one of the prime equivalences, and hence cannot satisfy the original, hence we have precisely $2^k$ solutions.